问题描述:
设有
n个顾客同时等待一项服务。顾客
i需要的服务时间为
ti,1<=ti<=n。共有
s处可以提供此项服务。应如何安排
n个顾客的服务次序才能使平均等待时间达到最小
? 平均等待时间是
n个顾客等待服务时间的总和除以
n。
#include<iostream>
#include<algorithm>
using namespace std;
const int lenn=10000;
const int lens=500;
int n,s;
int a[lenn];
int wait[lens];
int find()
{
int minTime=wait[0];
int pos=0;
for ( int i=1; i<s; i++ )
{
if ( minTime>wait[i] )
{
minTime=wait[i];
pos=i;
}
}
return pos;
}
int main()
{
while ( cin>>n>>s )
{
int i;
for ( i=0; i<n; i++ )
{
cin>>a[i];
}
sort ( a,a+n );
memset ( wait,0,sizeof ( wait ) );
double sum=0;
for ( i=0; i<n; i++ )
{
int t=find();
wait[t]+=a[i];
sum+=wait[t];
}
double res=sum/n;
printf ( "%.2f\n",res );
}
return 0;
}