P1223 排队接水

admin

https://www.luogu.org/problemnew/show/P1223

题目描述
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入输出格式
输入格式：
输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出格式：
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入输出样例
输入样例#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<=1e6，不保证ti不重复

当ti重复时，按照输入顺序即可（sort是可以的）

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int n,i,j;
   
6. double ans;
   
7. struct node
   
8. {
   
9.     int num,t;
   
10. } a[1010];
    
11. bool cmp(node x,node y)
    
12. {
    
13.     return x.t<y.t;
    
14. }
    
15. int main()
    
16. {
    
17.     cin>>n;
    
18.     for(i=1;i<=n;i++)
    
19.     {
    
20.         cin>>a[i].t;
    
21.         a[i].num=i;
    
22.     }
    
23.     sort(a+1,a+n+1,cmp);
    
24.     for(i=1;i<=n;i++)
    
25.     {
    
26.         ans+=a[i].t*(n-i);
    
27.         ///cout<<ans<<endl;
    
28.         cout<<a[i].num<<" ";
    
29.     }
    
30.     ans=ans/n;
    
31.     cout<<endl<<fixed<<setprecision(2)<<ans;
    
32.     return 0;
    
33. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n;
    
14. double all=0;
    
15. struct node
    
16. {
    
17.         int v,b;
    
18. }a[1020];
    
19. bool cmp(node x,node y)
    
20. {
    
21.         return x.v<y.v;
    
22. }
    
23. int main()
    
24. {
    
25.         scanf("%d",&n);
    
26.         for(int i=1;i<=n;i++)
    
27.                 scanf("%d",&a[i].v),a[i].b=i;
    
28.         sort(a+1,a+1+n,cmp);
    
29.         for(int i=1;i<=n;i++)
    
30.         {
    
31.                 printf("%d ",a[i].b);
    
32.                 all+=a[i].v*(n-i);
    
33.         }       
    
34.         printf("\n%.2lf",all/n);
    
35.     return 0;
    
36. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int n;
   
6. double ans;
   
7. struct ha
   
8. {
   
9.     int t,num;
   
10. }a[1001];
    
11. bool operator< (ha &x,ha &y)
    
12. {
    
13.     return x.t<y.t;
    
14. }
    
15. int main()
    
16. {
    
17.     cin>>n;
    
18.     for(int i=1;i<=n;i++)cin>>a[i].t,a[i].num=i;
    
19.     sort(a+1,a+n+1);
    
20.     for(int i=1;i<=n;i++)
    
21.     {
    
22.         cout<<a[i].num<<' ';
    
23.         ans+=a[i].t*(n-i);
    
24.     }
    
25.     cout<<endl<<fixed<<setprecision(2)<<ans/n;
    
26.     return 0;
    
27. }
    

复制代码