【题目来源】
AcWing：913. 排队打水 - AcWing题库
【题目描述】
有 \(n\) 个人排队到 \(1\) 个水龙头处打水，第 \(i\) 个人装满水桶所需的时间是 \(t_i\)，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
【输入】
第一行包含整数 \(n\)。
第二行包含 \(n\) 个整数，其中第 \(i\) 个整数表示第 \(i\) 个人装满水桶所花费的时间 。
【输出】
输出一个整数，表示最小的等待时间之和。
【输入样例】
7
3 6 1 4 2 5 7
【输出样例】
56
【算法标签】
《AcWing 913 排队打水》 #贪心# #排序不等式#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义宏，将 int 替换为 long long，方便处理大整数
const int N = 100005; // 定义数组的最大长度int n; // 任务的数量
int t[N]; // 存储每个任务的完成时间signed main() // 使用 signed main() 是为了兼容 #define int long long
{// 输入任务的数量cin >> n;// 输入每个人打水的时间for (int i = 0; i < n; i++) cin >> t[i];// 将打水完成时间按升序排序sort(t, t + n);int res = 0; // 用于存储最终的结果（最小总等待时间）// 计算打水的总等待时间for (int i = 0; i < n; i++) {// 对于第 i 个人，它的等待时间会被后面的 (n - i - 1) 个任务累加// 因此，它的贡献是 t[i] * (n - i - 1)res += t[i] * (n - i - 1);}// 输出最小总等待时间cout << res << endl;return 0;
}
【运行结果】
7
3 6 1 4 2 5 7
56