http://oi.hdoi.cn/training/2/problem/P1257
有 n 个人在一个水龙头前排队接水,假如每个人接水的时间为T
i
,请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。
共两行,第一行为n(1≤n≤1000);
第二行分别表示第1个人到第n个人每人的接水时间T
1
,T
2
,…,T
n
,每个数据之间有1个空格。
有两行,第一行为一种排队顺序,即1到n的一种排列;
第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
10
56 12 1 99 1000 234 33 55 99 812
3 2 7 8 1 4 9 6 10 5
532.00
update:2021.05.12: 提示:排序如果打水时间相同,按编号从小到大。
#include
using namespace std;
const int maxn=1e3+10;
int n;
double cnt;
struct node{
int x,op;
inline void input(){
scanf("%d",&x);
}
}a[maxn];
inline bool cmp(node u,node v){
if(u.x!=v.x)return u.x<v.x;
return u.op<v.op;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
a[i].input();
a[i].op=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
printf("%d ",a[i].op);
cnt=cnt+(n-i+1)*a[i].x;
}
cnt=cnt/(n*1.0);
printf("\n%.2lf\n",cnt);
return 0;
}