排队打水

思路分析

很常见的小学奥数，让时间短的人在前面，总消耗时间越短

所以步骤就是先将时间升序排列，最小的再最前面，然后计算

y总打卡代码为了省事，换了一个思路，因为时间最长的人后面没有人，不用等，所以按降序排列直接和下标相乘，这样也可以得到正确结果

证明

我们假设排队有$n$个人，第$k$个人的等待时间是$tk$，如上面y总图所示

这里反证法，如果时间不是升序，那么一定存在一个逆序对（y总上课说的是相邻逆序，这里应该是任意逆序均可），逆序对第一个数字大于第二个数字，我们可以发现，消除该逆序可以降低时间。所以时间是升序排列的

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int t[N]; // 存储时间

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

    sort(t, t + n); // 降序排序
    reverse(t, t + n); // 翻转

    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * i; // 时间最长的人不用等，第二长的有一个等……

    printf("%lld\n", res);

    return 0;
}