C++贪心——排队接水

题目描述

有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti​，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。

输入格式

第一行为一个整数 n。

第二行 n 个整数，第 i个整数 Ti​ 表示第 i 个人的等待时间 Ti​。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

分析：

最短的排队顺序应该是将小数放到后面，大数在后面。使后面的等待时间少一些。平均等待时间应该是，将每个人的等待时间乘上后面等待的人数在加一起除以人数。

代码：

#include
using namespace std;
struct jieshui
{int t;//等待时间int id;//序号
}ti[1100];
bool paixu(jieshui a, jieshui b) {if (a.t < b.t)return true;else return false;
}
int  main() {int n;double sum=0;cin >> n ;for (int i = 1; i <= n; i++) {cin >> ti[i].t;ti[i].id = i;}sort(ti + 1, ti + 1 + n, paixu);for (int i = 1; i <= n; i++) {cout << ti[i].id << " ";sum += ti[i].t * (n-i);}cout << endl;cout << fixed << setprecision(2);cout << sum/n;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！