本文主要是介绍C++ 贪心 排序不等式 排队打水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有 n
个人排队到 1
个水龙头处打水，第 i
个人装满水桶所需的时间是 ti
，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
输入格式
第一行包含整数 n
。
第二行包含 n
个整数，其中第 i
个整数表示第 i
个人装满水桶所花费的时间 ti
。
输出格式
输出一个整数，表示最小的等待时间之和。
数据范围
1≤n≤105
,
1≤ti≤104
输入样例：
7
3 6 1 4 2 5 7
输出样例：
56
贪心通用思路：
先猜一个做法，然后去证明或者测试正确。
证明：可以证明，图中前 - 后大于0，因此从小到大排序总时间最小。
主要就是理解并推出这个式子，代码很简单。
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n;
int a[N];int main ()
{scanf("%d", &n);for(int i = 0; i < n; i ++ )scanf("%d", &a[i]);sort(a, a + n);LL res = 0;for(int i = 1; i < n; i ++ )// 从a[1]开始，因为a[0]第一个人不需要等res += (LL)a[i - 1] * (n - i);printf("%lld\n", res);return 0;
}
这篇关于C++ 贪心 排序不等式 排队打水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
