t0ur1st

题目描述：

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

输入描述：

第一行有2个正整数n和s，表示有n个顾客且有s处可以提供顾客需要的服务。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。

输出描述：

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

输入样例：

10 2
56 12 1 99 1000 234 33 55 99 812

输出样例：

336

解题思路：

贪心算法。和最优服务次序问题的区别在于，这题是优先服务s个总等待时间最小的顾客。

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))
const int INF = 0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,s;  //n个顾客,s个服务点
    cin >> n >> s;
    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)
    {
        int k = 0,mind = INF;
        Up(j,1,s)   //s个服务点
        {
            if(mind > d[j])    //更新最小值,优先服务总等待时间最小的
            {
                mind = d[j];
                k = j;
            }
        }
        d[k] += a[i];   //每个顾客的等待总时间
        sum += d[k];
    }
    cout << setiosflags(ios::fixed) << setprecision(2) << sum/n << endl;    //保留俩位小数
    return 0;
}