（贪心）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）对于其排序时，要用pair或结构体，这样才能取下标。

2）注意等待时间，是除了正在取水的人外其他人所需要等待的时间。

C++代码：

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int maxn = 1003; typedef pair<int,int> pii; pii a[maxn]; bool cmp(pii a, pii b){ return a.first < b.first; } int main(){ int n; scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d",&a[i].first); a[i].second = i+1; } sort(a,a+n,cmp); double sum = 0.0; for(int i = 0;i < n;i++){ sum += a[i].first * (n - i - 1); printf("%d ",a[i].second); } printf("\n%.2lf\n",sum/n); return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10554092.html

相关资源：JAVA上百实例源码以及开源项目