洛谷 P1223 排队接水:有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti,请编程找出这 n 个人排队的一种顺序,使得 n 个人的平均等待时间最小。
输入输出格式
输入格式:
输入文件共两行,第一行为 n;第二行分别表示第 1 个人到第 n 个人每人的接水时间 T1,T2,…,Tn,每个数据之间有 1 个空格。
输出格式:
输出文件有两行,第一行为一种排队顺序,即 1 到 n 的一种排列;第二行为这种排列方案下的平均等待时间 (输出结果精确到小数点后两位)。
输入输出样例
输入样例 #1:
10
56 12 1 99 1000 234 33 55 99 812
输出样例 #1:
3 2 7 8 1 4 9 6 10 5
291.90
- #include#include#include using namespace std;
- const int maxn = 1001;
- struct P {
- int t,
- r;
- }
- p[maxn];
- int cmp(P a, P b) {
- return a.t < b.t;
- }
- int main() {
- int n;
- double sum = 0.00;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> p[i].t;
- p[i].r = i;
- }
- sort(p + 1, p + n + 1, cmp);
- for (int i = 1; i <= n; i++) {
- cout << p[i].r << " ";
- sum += p[i].t * (n - i);
- }
- printf("\n%.2f\n", sum / n);
- return 0;
- }
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: