Hust oj 1184 早起一水(简单贪心）

n个人排队接水，编号为1到n，每个人的接水时间为Ti，请编程找出这n个人的排队序列（接水时间的一样的按照他们的编号排队），使得他们的平均等待接水时间最小。

1 <= n <= 100000。

0 <= Ti <= 200000。

有多组测试数据。

对于每组测试数据，第一行为n，表示有n个人。第二行为n个数Ti， 表示第i个人的接水时间。

输出共两行。

第一行输出n个人的排队序列，每两个数之间有一个空格。

第二行为这种排队序列下的最小平均等待时间，保留到小数点后两位。

1.50

简单贪心，谁花的时间少谁先接水 (标题就已经说明了这题有多水= =。。。）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;struct water
{int key;int cost;
}c[100005];int cmp(water x,water y)
{if(x.cost == y.cost)return x.key < y.key;elsereturn x.cost < y.cost;
}int main()
{int n;while(~scanf("%d",&n)){for(int i = 0; i < n; i++){scanf("%d",&c[i].cost);c[i].key = i + 1;}sort(c,c+n,cmp);double sum = 0;double ans = 0;printf("%d ",c[0].key);for(int i = 1; i < n-1; i++){sum += c[i].cost;ans += sum;printf("%d ",c[i].key);}printf("%d\n%.2lf\n",c[n-1].key,(ans-c[0].cost)/n+1);}
}