排队打水

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

Input

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

Output

平均等待时间(输出结果精确到小数点后两位)。

Sample Input

10
56 12 1 99 1000 234 33 55 99 812

Sample Output

291.90



sol:贪心（交换法），我们先假设只有2个人a，b排队打水，不妨设接水的时间timea<timeb,如果a在b前面打水，则总时间为timea+(timea+timeb)，如果b在a前面，则总时间为timeb+(timeb+timea)，因为timea<timeb，所以a在b前面更优。当然你也可以设有多个人，发现交换a，b的顺序对a，b前后的人用时是没有影响的。所以我们只需要按照每个人打水时间从小到大进行排序，先后打水就可以了。本题贪心策略明显。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,a[1010];
 6 int main() 
 7 {
 8     scanf("%d",&n);
 9     for(int i=1; i<=n; i++)
10         scanf("%d",&a[i]);
11     sort(a+1,a+n+1);
12     double sum=0;
13     for(int i=1; i<=n; i++)     
14     {
15         sum+=(n-i)*a[i];
16     }
17  
18     printf("%.2lf",sum/n);
19     return 0;
20 }