排队打水
- 贪心问题的一般证明的两种方法
- 反证法
- 数学归纳法 ans >= cnt, cnt >= ans => ans == cnt
- 有 n 个人打水，每个人打水时间为t(i), 求如何排列打水顺序，让总的等待时间最短。
思路
- 让最墨迹的人排在最后
- 让打水时间最快的排在最前边
#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);
LL res = 0;
for (int i = 0; i < n; i++)
{
res += t[i] * (n - i - 1);
}
printf("%lld", res);
return 0;
}
