1307 排队接水
1307 排队接水
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、for循环、printf、long long
有 个人()在一个水龙头前排队接水,第 个人接水需要 时间。
每个人都要等他前面的人全部接完才能开始接水。请找出一种排队顺序,使得 个人的平均等待时间最小。
补充说明:一个人的"等待时间"是指他排了多久才轮到自己开始接水(不含他自己的接水时间)。平均等待时间 = 所有人的等待时间之和 。
输入格式:
- 第 1 行:一个整数
- 第 2 行: 个整数
输出格式:
- 第 1 行: 个整数(1 到 的排列),表示最优排队顺序(人的原始编号)
- 第 2 行:平均等待时间,精确到小数点后两位
样例:
输入:
10
56 12 1 99 1000 234 33 55 99 812
输出:
3 2 7 8 1 4 9 6 10 5
291.90二、解题思路
数据规模分析
, 的排序完全足够。时间数值可能较大(样例中有 1000),累加时注意用 long long 或 double。
算法选择:贪心
要让平均等待时间最小,关键是想清楚一个人的等待时间由什么决定。
假设排好队后,顺序为 :
- 第 1 个人:等待时间 =
- 第 2 个人:等待时间 =
- 第 3 个人:等待时间 =
- 第 个人:等待时间 =
所有人的等待时间之和:
可以直观地看出:排在前面的人,他的接水时间会被后面很多人"等待"很多次。因此,为了让总等待最小,接水时间短的人应该排在前面,这样他"拖累"别人的次数少。
这就是贪心策略:按接水时间从小到大排序。排序后计算等待时间即可。
为什么贪心正确?交换论证:假设最优顺序中,某两个相邻的人 在后面、 在前面,但 。交换他俩的位置, 后面的人等待时间都会减少 (因为前面少了一个耗时长的人),而 后面的人不受影响(因为 的耗时和原来 的耗时抵消,但实际不是这么简单)——更严谨地说,交换相邻的两个逆序对不会使总等待增加,因此按升序排列必为最优。
算法流程
- 读入 和每个人的
- 用结构体记录每个人的原始编号和接水时间
- 按接水时间从小到大排序
- 按排序后的顺序,依次计算:
- 输出该人的原始编号
- 累加等待时间:当前总等待 += 前面已接水时间之和(即当前这个人的等待时间)
- 更新前面已接水时间之和 += 该人的接水时间
- 平均等待时间 = 总等待时间 / ,用
printf("%.2f", ...)输出
手动模拟
样例中 10 个人的时间:56, 12, 1, 99, 1000, 234, 33, 55, 99, 812
排序(升序):1(3号), 12(2号), 33(7号), 55(8号), 56(1号), 99(4号), 99(9号), 234(6号), 812(10号), 1000(5号)
计算等待:
- 3 号:等 0,前面累计 = 1
- 2 号:等 1,前面累计 = 1+12 = 13
- 7 号:等 13,前面累计 = 13+33 = 46
- 8 号:等 46,前面累计 = 46+55 = 101
- 1 号:等 101,前面累计 = 101+56 = 157
- 4 号:等 157,前面累计 = 157+99 = 256
- 9 号:等 256,前面累计 = 256+99 = 355
- 6 号:等 355,前面累计 = 355+234 = 589
- 10 号:等 589,前面累计 = 589+812 = 1401
- 5 号:等 1401
总等待 = 0+1+13+46+101+157+256+355+589+1401 = 2919
平均 = 2919 / 10 = 291.9
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
struct Person {
int id; // 原始编号
int t; // 接水时间
};
Person a[N];
// 按接水时间升序排序
bool cmp(Person x, Person y) {
return x.t < y.t;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].t;
a[i].id = i; // 记录原始编号
}
// 按接水时间从小到大排序
sort(a + 1, a + n + 1, cmp);
// 输出排队顺序
for (int i = 1; i <= n; i++) {
cout << a[i].id << " ";
}
cout << endl;
// 计算平均等待时间
long long sum = 0; // 前面所有人的接水时间累计
long long total = 0; // 所有人的等待时间之和
for (int i = 1; i <= n; i++) {
total += sum; // 第 i 个人的等待时间 = 前面所有人的接水时间之和
sum += a[i].t; // 这个人的接水时间加到累计中,留给后面的人
}
double avg = (double)total / n;
printf("%.2f\n", avg);
return 0;
}四、复杂度分析
- 时间复杂度:。排序占主导,,非常快。
- 空间复杂度:。需要一个结构体数组存储 个人的信息。
易错点:
- 输出排队顺序时,输出的是原始编号而不是排序后的位置,所以必须用结构体存原始编号。
- 注意等待时间不包括自己接水的时间——第 个人的等待时间是他前面所有人的接水时间之和。
- 累加等待时间时, 且 可能很大,等待时间总和可能超过
int范围,用long long更安全。
