B1228 排队打水问题
B1228 排队打水问题
【算法标签】 贪心
【语法标签】 :数组、sort、for循环、long long、cin/cout
有 个人排队到 个水龙头去打水(,),第 个人装满水桶需要 分钟()。
每人花费的总时间 = 排队等待时间 + 自己打水的时间。切换过程不消耗时间,即前一个人打完的瞬间,下一个人就可以开始。
求:合理安排排队顺序,使所有人花费的总时间最少。
输入格式:
- 第 1 行:两个整数 和
- 第 2 行: 个整数
输出格式:
- 一个整数,表示最少总时间
样例:
输入:
4 2
2 6 4 5
输出:
23样例解释:
有 2 个水龙头,4 个人的打水时间为 [2, 6, 4, 5]。
最优安排:
- 水龙头 1:先打 2 分钟,再打 6 分钟
- A 花 2 分钟(等 0 + 打 2)
- B 花 8 分钟(等 2 + 打 6)
- 水龙头 2:先打 4 分钟,再打 5 分钟
- C 花 4 分钟(等 0 + 打 4)
- D 花 9 分钟(等 4 + 打 5)
总时间 = 2 + 8 + 4 + 9 = 23。
二、解题思路
数据规模分析
,。,最坏情况下总时间约为 ,在 int 范围内(约 ),但保险可以用 long long。
问题本质
这是经典的多服务台排队问题。本质是把 个任务分配到 个队列,每个队列内按"短任务优先"排序,使得总的完成时间之和最小。
算法选择:贪心
贪心策略分两步:
第一步:排序。不管分配到哪个水龙头,同一个水龙头上排队的人,一定是接水时间短的排在前面更优。理由和单水龙头排队一样——短任务优先能减少后面人的等待时间。所以先把所有人按 从小到大排序。
第二步:分配。排序后,依次将每个人分配到"当前最空闲"的水龙头。具体做法是:维护一个数组 tap[i] 表示第 个水龙头当前累计的处理时间(即这个水龙头上已安排的所有人的打水时间之和)。每次取 tap 中最小的那个水龙头,将下一个人分配过去。
为什么分配到"最空闲"的水龙头?因为这样可以让等待时间尽量均匀分布,避免某个水龙头积压太多人。
算法流程
- 读入 和 个
- 对 数组从小到大排序
- 初始化 个水龙头的当前累计时间
tap[1..r] = 0 - 初始化总时间
ans = 0 - 遍历排序后的每个人:
- 找到当前
tap值最小的水龙头编号k(即最空闲的) - 该人的花费时间 =
tap[k] + t[i](等待 tap[k] 分钟 + 自己打 t[i] 分钟) ans +=该人的花费时间tap[k] += t[i](更新该水龙头的累计时间)
- 找到当前
- 输出
ans
等一下,我们需要再想一想。实际上,如果我们把最短的 r 个任务分别放到 r 个水龙头上,然后每个人在水龙头上的花费时间 = 该水龙头当前时间 + 自己的打水时间。实际上等价于:对每个水龙头,就是把分配到它上面的人按时间排好,然后计算每个人的打完时间(从 0 开始计),求和。
更简单的理解:排序后,第 1 到第 r 个人分别占据 r 个水龙头的第一个位置,第 r+1 到第 2r 个人分别占据各水龙头的第二个位置,以此类推。这样,第 i 个水龙头上第 j 个人的等待时间就是他前面 j-1 个人的打水时间之和(都在这个水龙头上)。
另一种写法(更直观):排序后,模拟每个水龙头的队列。对每个水龙头维护 cur[i] = 当前这个水龙头的累计时间(即这个水龙头上已安排的总打水时间)。对于每个人,找到 cur 最小的水龙头,该人的完成时间 = cur[min] + t[i](注意!这里我混淆了两个概念,让我重新理清)。
对于每个人来说:
- 他的花费时间(题目要求的东西)= 他等待的时间 + 他打水的时间 = 他前面的累计打水时间 + 他自己的打水时间
- 如果他被分配到水龙头 k,且水龙头 k 当前的累计时间为
cur[k],则:- 他的等待时间 =
cur[k] - 他的打水时间 =
t[i] - 他的花费 =
cur[k] + t[i] - 之后更新
cur[k] += t[i]
- 他的等待时间 =
这和单水龙头的情况本质相同——每个水龙头内部的人,等待时间就是前面所有人的时间之和。
这样一直模拟到所有人都分配完即可。
手动模拟样例
- 排序:
- 初始:
cur[1]=0, cur[2]=0 - 第 1 人(t=2):分配到水龙头 1(cur[1]=0 最小)
- 花费 = 0 + 2 = 2
- cur[1] = 0 + 2 = 2
- ans = 2
- 第 2 人(t=4):分配到水龙头 2(cur[2]=0 最小)
- 花费 = 0 + 4 = 4
- cur[2] = 0 + 4 = 4
- ans = 6
- 第 3 人(t=5):分配到水龙头 1(cur[1]=2 < cur[2]=4)
- 花费 = 2 + 5 = 7
- cur[1] = 2 + 5 = 7
- ans = 13
- 第 4 人(t=6):分配到水龙头 2(cur[2]=4 < cur[1]=7)
- 花费 = 4 + 6 = 10
- cur[2] = 4 + 6 = 10
- ans = 23
输出 23,和样例一致。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int R = 105;
int t[N]; // 每个人的打水时间
int cur[R]; // cur[i] 表示第 i 个水龙头的当前累计时间
int main() {
int n, r;
cin >> n >> r;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
// 第一步:按打水时间从小到大排序(短任务优先)
sort(t + 1, t + n + 1);
// 第二步:依次分配每个人到最空闲的水龙头
long long ans = 0;
for (int i = 1; i <= n; i++) {
// 找到当前累计时间最小的水龙头
int k = 1; // 最空闲的水龙头编号
for (int j = 2; j <= r; j++) {
if (cur[j] < cur[k]) {
k = j;
}
}
// 第 i 个人分配到水龙头 k
// 他的等待时间 = cur[k](前面的人打水时间之和)
// 他的总花费 = cur[k] + t[i]
ans += cur[k] + t[i];
// 更新该水龙头的累计时间
cur[k] += t[i];
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。排序 ,每次分配需要 找最小水龙头,共 次分配,所以分配部分 。,,最多 次比较,完全没问题。如果数据更大,可以用优先队列(小根堆)优化到 。
- 空间复杂度:。数组 大小为 ,数组 大小为 。
知识扩展:优先队列优化
当 和 更大时,可以用**小根堆(priority_queue)**来维护每个水龙头的累计时间,每次取最小值的操作变成 。以下为优化版代码:
// 优化版:用小根堆维护各水龙头累计时间
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= r; i++) {
pq.push(0); // 初始所有水龙头时间为 0
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
int cur_min = pq.top(); pq.pop(); // 最空闲的水龙头
ans += cur_min + t[i];
pq.push(cur_min + t[i]);
}易错点:
- 本题的"花费时间"= 等待时间 + 打水时间,注意和 1307 排队接水(只算等待时间)的区别。
- 排序方向是从小到大(短任务优先),不要排反。
- 当 时,水龙头比人多,每人直接占一个水龙头,总花费 = 所有人的 之和(无需等待)。
