有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti,请编程找出这 n 个人排队的一种顺序,使得 n 个人的平均等待时间最小。
输入格式第一行为一个整数 n。
第二行 n 个整数,第 ii 个整数 Ti 表示第 i 个人的等待时间 Ti。
输出格式输出文件有两行,第一行为一种平均时间最短的排队顺序;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
输入输出样例输入 #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说明/提示
n≤1000,ti≤10^6,不保证 ti 不重复。
当 ti 重复时,按照输入顺序即可(sort 是可以的)
【分析】
先sort排序一遍,输出值,再算平均值。
【AC代码】
#include#include #include using namespace std; struct peo { int id, t; }a[1100]; bool cmp(peo x, peo y) { return x.t < y.t; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].t; a[i].id = i; } sort(a + 1, a + 1 + n, cmp); for (int i = 1; i <= n; i++) { cout << a[i].id << " "; } cout << endl; long long cnt = 0, ans = 0; //得开long long不然有两个测试点过不去 for (int i = 1; i <= n; i++) { ans += cnt; cnt += a[i].t; } printf("%.2lf", ans / (n * 1.0)); // 别忘×1.0 return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)