Acwing 913.排队打水题解

Acwing 913.排队打水

思路：

可以得出当排队时间按升序打水，等待时间最短

---

数学证明：

反证法

有n个人，对第i个和第i+1个打水的人，他们的打水时间为 $t_i$, $t_{i+1}$ ($t_i$ < $t_{i+1}$)

若按升序打水时间$T_1$ = $t_i$ * (n - i) + $t_{i+1}$ * (n-i-1)

若两者顺序转换: $T_2$ = $t_{i+1}$ * (n - i) + $t_i$ * (n - i - 1)

$T_1$ - $T_2$ = $t_i$ - $t_{i+1}$ < 0

以此类推可知升序时间最小

---

c++代码

/*
 * @Author: Awesome_ZC 
 * @Date: 2021-08-29 15:22:21 
 * @Version: 1.0
 */


#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) 
        scanf("%d", &a[i]);

    sort(a, a + n);

    LL ans = 0;
    for(int i = n -1, j = 0; i >= 1; i --, j ++)
        ans += i * a[j];

    cout << ans << endl;
    return 0;
}