「RQNOJ255」排队接水
题目描述
有n个人在一个水龙头前排队接水,假如每个人接水的时间为t[i],请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。
注意:若两个人的等待时间相同,则序号小的优先。
输入格式第一行为n。
第二行到最后一行中,共有n个整数,
分别表示第一个人到第n个人每人的接水时间t[1],t[2],t[3],t[4],……t[n],每个数据之间有一个空格或换行。
数据范围: 0<n<=900, 0<t<=1000
输出格式共两行,第一行为一种排队顺序,即1到n的一种排列;第二行为这种排列方案下的平均等待时间(保留到小数点后第二位)。
样例输入
10
56 12 1 99 1000 234 33 55 99 812
输出
3 2 7 8 1 4 9 6 10 5
291.90
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct data{ int t,num; }a[901]; int gz(const data &a,const data &b) { if(a.t>b.t||a.t==b.t&&a.num>b.num)return 0; return 1; } int main() { int n; float ans=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].t; a[i].num=i; } sort(a+1,a+n+1,gz); for(int i=1;i<=n;i++) { cout<<a[i].num; ans+=a[i].t*(n-i); if(i!=n)cout<<' '; } cout<<endl; printf("%.2f",ans/n); return 0; } |
Subscribe