题目描述

有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

样例

7
3 6 1 4 2 5 7

56

算法

(贪心)

时间复杂度

$O(nlogn)$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);

    // int res = 0, t = 0;
    LL res = 0, t = 0;
    for(int i = 0; i < n; i ++)
    {
        res += t;
        t += a[i];
    }

    cout << res;
    return 0;
}