华师一附中OI组

标题: P1223 排队接水 [打印本页]
作者: admin    时间: 2018-5-11 17:21
标题: P1223 排队接水
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是可以的）

作者: 倚窗倾听风吹雨    时间: 2018-7-20 16:14
  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. }
复制代码
作者: 吴语林    时间: 2018-7-29 19:42
  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. }
复制代码
作者: 黄煦喆    时间: 2018-10-18 21:53
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2