【题目来源】
洛谷：P1223 排队接水 - 洛谷 (luogu.com.cn)
【题目描述】
有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。
【输入】
第一行为一个整数 \(n\)。
第二行 \(n\) 个整数，第 \(i\) 个整数 \(T_i\) 表示第 \(i\) 个人的等待时间 \(T_i\)。
【输出】
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
【输入样例】
10
56 12 1 99 1000 234 33 55 99 812
【输出样例】
3 2 7 8 1 4 9 6 10 5
291.90
【解题思路】
【算法标签】
《洛谷 P1223 排队接水》 #贪心# #排序#
【代码详解】
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;// 定义人员结构体
struct people
{int time; // 该人员完成任务所需时间int num; // 人员编号
} ps[1005]; // 最多1005人// 自定义排序比较函数：按完成任务时间升序排序
bool cmp(people p1, people p2)
{return p1.time < p2.time;
}int main()
{int n; // 总人数double sum = 0; // 总等待时间double avg; // 平均等待时间// 输入总人数cin >> n;// 输入每个人的任务完成时间，并记录人员编号for (int i = 1; i <= n; i++) {cin >> ps[i].time;ps[i].num = i;}// 按任务完成时间从短到长排序sort(ps + 1, ps + n + 1, cmp);// 输出最优排队顺序for (int i = 1; i <= n; i++) {cout << ps[i].num << " ";// 计算该人员后面所有人的等待时间sum += (n - i) * ps[i].time;}cout << endl;// 计算并输出平均等待时间（保留两位小数）avg = sum / n;printf("%.2f", avg);return 0;
}
【运行结果】
10
56 12 1 99 1000 234 33 55 99 812
3 2 7 8 1 4 9 6 10 5
291.90