Optimal Services

Time Limit:1000MS  Memory Limit:65536K
Total Submit:454 Accepted:328

Description

设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ，1 ≤ i ≤ n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。
编程任务：
对于给定的n个顾客需要的服务时间，编程计算最优服务次序。

Input

输入由多组测试数据组成。
每组测试数据输入的第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。

Output

对应每组输入，输出的每行是计算出的最小平均等待时间。

Sample Input

10
56 12 1 99 1000 234 33 55 99 812

Sample Output

532.00

#include <iostream>
#include <algorithm>
#define MAX 10001
using namespace std;

bool GY (double a , double b)
{
        return a < b;
}

int main()
{
        int n , j;
        double sum , k , p[ MAX ];

        while (scanf ("%d" , &n) == 1)
        {
                for (j = 1 ; j <= n ; ++ j)
                        scanf ("%lf" , &p[ j ]);

                sort (p + 1 , p + n + 1 , GY);
                k = sum = 0;
                for (j = 1 ; j <= n ; ++ j)
                {
                  sum += k + p[ j ];
                  k += p[ j ];
                }
                printf ("%.2f\n" , sum / n);
        }
        return 0;
}