t0ur1st

题目描述：

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

输入描述：

第1行是正整数n，表示有n个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。

输出描述：

计算出来的最小平均等待时间。

输入样例：

10
56 12 1 99 1000 234 33 55 99 812

输出样例：

532.00

解题思路：

贪心算法。sort就完事了，优先对所需服务时间较短的顾客进行服务。每个顾客的等待时长是排在他前面的所有顾客的服务时长加上他自己所需要的服务时长。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;  //n个顾客
    cin >> n;
    int a[n+1];  //a用来存放每个顾客需要的服务时间
    ms(a,0);
    Up(i,1,n)
    {
        cin >> a[i];
    }
    sort(a+1,a+1+n);    //升序排列
    int d[n+1];   //d用来存放第i个客户的总等待时间
    ms(d,0);
    double sum = 0;
    Up(i,1,n)
    {
        Up(j,i,n)
        {
            d[j] += a[i];
        }
        sum += d[i];
    }
    cout << setiosflags(ios::fixed) << setprecision(2) << sum/n << endl;    //保留俩位小数
    return 0;
}