【算法】最优服务次序问题（贪心算法）

算法】最优服务次序问题（贪心算法）"/>

【算法】最优服务次序问题（贪心算法）

设有n 个顾客同时等待一项服务。顾客i需要的服务时间为 t i​ (1<=i<=n) 。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n 个顾客等待服务时间的总和除以n。

输入格式:
第一行是正整数n(1<n<1000)，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。

输出格式:
计算出的最小平均等待时间，保留两位小数。

输入样例:

10

56 12 1 99 1000 234 33 55 99 812

输出样例:

291.90

问题分析
易知第一个客人等待时间为0；要想所有客人等待时间最短，就先服务时间短的客人，则其他客人的等待时间是上一个客人等待的时间加上上一个客人服务的时间。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;int main()
{int n;//n个客户cin>>n;int a[n],num[n];for(int i=0;i<n;i++){cin>>a[i];}num[0]=0;//第一个顾客等待时间int i,time=0;sort(a,a+n);for(i=1;i<n;i++){num[i]=num[i-1]+a[i-1];}for(i=0;i<n;i++){time=time+num[i];}printf("%.2lf", 1.0*time/n);}