有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
10
56 12 1 99 1000 234 33 55 99 812
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 }
原文：https://www.cnblogs.com/cutepota/p/12133458.html