【贪心】排队接水
<center>
提交: 38 解决: 20
[提交][状态][讨论版] </center>
问题 C: 【贪心】排队接水
时间限制: 1 Sec 内存限制: 128 MB提交: 38 解决: 20
[提交][状态][讨论版] </center>
题目描述
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
输入
共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出
有两行，第一行为一种排队顺序，即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
代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef struct node{ int t; int cou; }; node a[1000]; int cmp(node a,node b){ return a.t<b.t; } int main() { int n; int every=0; double avg; int sum=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i].t); a[i].cou=i+1; } sort(a,a+n,cmp); for(int i=0;i<n;i++){ if(i==n-1){ printf("%d\n",a[i].cou); }else{ printf("%d ",a[i].cou); } if(i!=0){ every+=a[i-1].t; } sum+=every; } avg=sum*1.0/n; printf("%.2f",avg); return 0; }
查看6道真题和解析