A26391. 排队序列
填空题
困难
知识点
题目描述
排队序列
题目描述
已知现在有 n 个人需要打电话，他们已经排好了队伍，每个人打电话的时间为Ti。请你帮助他们找到一个排队打电话的队列方案，使队伍的平均等待时间更短。
输入格式
第一行：一个正整数n，表示一共n个人。
第二行：n个数字，分别表示第1个人到第n个人每人的打电话时间 T1，T2，…，Tn，每个数据之间有1个空格。
输出格式
第一行为一种排队顺序，即原先队列编号1到n的一种排列；
第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位，按照C语言的浮点数保留规则进行保留）。
输入样例
10
56 12 1 99 1000 234 33 55 99 812输出样例
3 2 7 8 1 4 9 6 10 5
291.90说明提示
1≤n≤100000，1≤Ti≤1000000
如果有多种排列都可以让平均等待时间最短，则输出其中字典序最小的序列。字典序指的是英文单词在字典中排序使用的规则顺序。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Person {
int id;
int time;
};
bool cmp(const Person &a, const Person &b) {
if(a.time != b.time) return a.time < b.time;
return a.id < b.id;
}
int main() {
int n;
cin >> n;
vector<Person> people(n);
for(int i = 0; i < n; i++) {
cin >> people[i].time;
people[i].id = i + 1;
}
sort(people.begin(), people.end(), cmp);
long long total_wait = 0;
long long current_wait = 0;
for(int i = 0; i < n; i++) {
if(i > 0) cout << " ";
cout << people[i].id;
if(i > 0) current_wait += people[i-1].time;
total_wait += current_wait;
}
cout << endl;
double avg_wait = (double)total_wait / n;
cout << fixed << setprecision(2) << avg_wait << endl;
return 0;
}
上一题
下一题