排队接水
题目描述
有 $n$ 个人在一个水龙头前排队接水,假如每个人接水的时间为 $T_i$,请编程找出这 $n$ 个人排队的一种顺序,使得 $n$ 个人的平均等待时间最小。
输入格式
第一行为一个整数 $n$。
第二行 $n$ 个整数,第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$。
输出格式
输出文件有两行,第一行为一种平均时间最短的排队顺序;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
样例 #1
样例输入 #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 \leq 1000,t_i \leq 10^6$,不保证 $t_i$ 不重复。
当 $t_i$ 重复时,按照输入顺序即可(sort 是可以的)
思路
先让耗时的先打水,有最小平均等待时间。
AC代码
#include <iostream>
#include <algorithm>
#include <iomanip>
#define AUTHOR "HEX9CF"
using namespace std;
const int maxn = 100005;
struct S{
int n;
int t;
}a[maxn];
bool cmp(S x, S y){
return x.t < y.t;
}
int main(){
int n;
double sum = 0, sgl = 0, avg = 0;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i].t;
a[i].n = i + 1;
}
sort(a, a + n, cmp);
for(int i = 0; i < n; i++){
if(i){
cout << " ";
}
cout << a[i].n;
if(i){
sgl += a[i - 1].t;
sum += sgl;
}
}
cout << endl << setiosflags(ios::fixed) << setprecision(2) << sum / n << endl;
return 0;
}