按接水时间从小到大排序，时间相同按编号从小到大，累加每个人开始前的等待时间。
OJ: luogu
题目 ID: P1223
难度:入门
标签:贪心排序python
日期: 2026-07-15 22:30
题意
给定每个人接水所需时间，安排排队顺序，使平均等待时间最小。等待时间不包括自己的接水时间。
思路
让接水时间短的人先接水，可以减少后面所有人的等待总量。因此按接水时间从小到大排序。
若两人时间相同，题目要求编号小的人在前。把每个人保存成：
text
(time, id)Python 元组排序自然先按时间，再按编号。
计算等待时间时，维护已经过去的时间 elapsed。每个人的等待时间就是他开始接水前的 elapsed。
Python 知识
people.sort()会按元组第一项、第二项依次排序。print(*order)可以输出编号序列。f"{total_wait / n:.2f}"输出平均等待时间，保留两位小数。
参考笔记：
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
代码
python
n = int(input())
times = list(map(int, input().split()))
people = [(times[index], index + 1) for index in range(n)]
people.sort()
order = [person_id for _, person_id in people]
total_wait = 0
elapsed = 0
for time, _ in people:
total_wait += elapsed
elapsed += time
print(*order)
print(f"{total_wait / n:.2f}")cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
/* P1223 排队接水 */
/* 接水时间短的人先接水，总等待时间最小。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
// 保存每个人的接水时间和编号
int t[MAXN], id[MAXN], idx[MAXN];
// 排序规则：时间小的在前，时间相同编号小的在前
bool cmp(int a, int b) {
if (t[a] != t[b]) return t[a] < t[b];
return id[a] < id[b];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i];
id[i] = i;
idx[i] = i;
}
sort(idx + 1, idx + n + 1, cmp);
long long total = 0; // 总等待时间
long long elapsed = 0; // 已经过去的时间
for (int i = 1; i <= n; i++) {
int p = idx[i];
// 当前人的等待时间 = 已经过去的时间
total += elapsed;
elapsed += t[p];
}
// 输出接水顺序
for (int i = 1; i <= n; i++) {
cout << id[idx[i]] << " \n"[i == n];
}
// 输出平均等待时间
printf("%.2f\n", (double)total / n);
return 0;
}复杂度
排序时间复杂度为
总结
这题是最短处理时间优先的贪心模型。排序键 (time, id) 正好对应题目的全部比较规则。