【GESP】C++四级/五级练习题 luogu-P1223 排队接水
GESP C++ 四级/五级练习题，贪心思想思想考点。题目难度⭐⭐★☆☆，适合五级入门和四级练习，洛谷难度等级普及-。
luogu-P1223 排队接水
题目要求
题目描述
有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。
一个人的等待时间不包括他的接水时间。
如果两个人接水的时间相同，编号更小的人应当排在前面。
输入格式
第一行为一个整数 $n$。
第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
输入输出样例 #1
输入 #1
1
2
10
56 12 1 99 1000 234 33 55 99 812
输出 #1
1
2
3 2 7 8 1 4 9 6 10 5
291.90
说明/提示
$1\le n \leq 1000$，$1\le t_i \leq 10^6$，不保证 $t_i$ 不重复。
题目分析
这是一道典型的贪心算法题目。
1. 问题分析
题目要求使 $n$ 个人的平均等待时间最小。因为 $n$ 是固定的，要使平均值最小，实际上就是要使总等待时间最小。
假设 $n$ 个人按某个顺序排队，接水时间分别为 $t_1, t_2, \dots, t_n$。
- 第 1 个人接水时，后面 $n-1$ 个人在等待，耗时 $t_1 \times (n-1)$。
- 第 2 个人接水时，后面 $n-2$ 个人在等待，耗时 $t_2 \times (n-2)$。
- …
- 第 $i$ 个人接水时，后面 $n-i$ 个人在等待，耗时 $t_i \times (n-i)$。
总等待时间 $S = \sum_{i=1}^{n} t_i \times (n-i)$。
2. 贪心策略
观察公式可以发现，越靠前的人，其接水时间 $t_i$ 被计算的次数越多（系数 $n-i$ 越大）。为了让总和 $S$ 最小，我们需要让耗时短的人排在前面，耗时长的人排在后面。即：按接水时间从小到大排序。
3. 细节处理
- 排序规则：题目要求“如果两个人接水的时间相同，编号更小的人应当排在前面”。因此在排序比较函数中，除了比较时间
time，还要处理time相等时比较id的情况。 - 数据范围：$n \le 1000, t_i \le 10^6$。总等待时间可能会达到 $1000 \times 1000 \times 10^6 / 2 \approx 5 \times 10^{11}$，超过了
int的表示范围（约 $2 \times 10^9$），因此累加变量sum必须使用long long类型。 - 输出格式：平均等待时间需要保留两位小数，可以使用
printf("%.2f", ...)或fixed+setprecision(2)。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <iomanip>
#include <iostream>
typedef long long ll;
// 定义结构体Water，用于存储每个人的编号和接水时间
struct Water {
int id; // 人的编号
int time; // 接水所需时间
};
// 比较函数：按照接水时间从小到大排序
// 如果接水时间相同，则按照编号从小到大排序
bool cmp(Water a, Water b) {
if (a.time == b.time) {
return a.id < b.id;
}
return a.time < b.time;
}
struct Water t[1005]; // 数组大小大于1000，符合题目范围
int main() {
int n;
std::cin >> n;
for (int i = 1; i <= n; i++) {
t[i].id = i; // 记录初始编号
std::cin >> t[i].time; // 输入接水时间
}
// 贪心策略：接水时间越短的人排在越前面，能使后续所有人的等待时间总和最小
std::sort(t + 1, t + n + 1, cmp);
ll sum = 0;
for (int i = 1; i <= n; i++) {
std::cout << t[i].id << " ";
// 计算总等待时间：
// 第i个人接水时，排在他后面的 n-i 个人都在等待
// 因此第i个人的时间贡献了 (n-i) 次等待
sum += t[i].time * (n - i);
}
std::cout << "\n";
// 输出平均等待时间，保留两位小数
std::cout << std::setprecision(2) << std::fixed << (double)sum / n;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
