解题思路

有 n 个人排队到 r 个水龙头打水，每个人打水的时间不一样，要让所有人的总时间（排队时间 + 打水时间）最少。

贪心思路：打水快的先打。

为什么？如果让打水慢的人先打，那么排在他后面的人都要等他很久，白白浪费时间。所以把打水时间从短到长排序，短的人先去打。

怎么安排到 r 个龙头？

排序后，第 1 个去第 1 个龙头，第 2 个去第 2 个龙头，…… 轮流分配。这样每个龙头排队的人都是按时间短的在前。

总时间怎么算？

用 wait 数组记录每个龙头已经累计的打水时间。轮到某个人时：

• 他的总时间 = 他所在龙头当前的累计时间（他排队等的）+ 他自己打水的时间
• 加进总和后，把这个人的打水时间累加到该龙头

举个例子：4 人 2 龙头，时间 2 6 4 5。

排序后：2 4 5 6

• 2 去龙头1：等0 + 打2 = 2，龙头1累计2
• 4 去龙头2：等0 + 打4 = 4，龙头2累计4
• 5 去龙头1：等2 + 打5 = 7，龙头1累计7
• 6 去龙头2：等4 + 打6 = 10
• 总时间 = 2+4+7+10 = 23 ✅

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, r;
	cin >> n >> r;
	
	int t[500];
	for (int i = 0; i < n; i++) cin >> t[i];
	
	// 打水时间短的先打，总时间最少
	sort(t, t + n);
	
	// wait[k] 记录第 k 个龙头已累计的时间
	int wait[100] = {0};
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int k = i % r;  // 轮流分配到每个龙头
		sum += wait[k] + t[i];  // 这个人等待 + 打水
		wait[k] += t[i];
	}
	
	cout << sum << endl;
	return 0;
}

复杂度分析

• 时间复杂度：O(N²)，冒泡排序
• 空间复杂度：O(N)，存时间和水龙头累计时间