多处最优服务次序问题
时间： 1ms 内存：64M
描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为t i，1≤i≤n。共有s处可以提供此项服务。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。
对于给定的n 个顾客需要的服务时间和s的值，计算最优服务次序。
输入：
输入数据的第一行有2 个正整数n （n≤10000）和s（s≤1000），表示有n 个顾客且有s 处可以提供顾客需要的服务。接下来的1 行中，有n个正整数，表示n个顾客需要的服务时间。
输出：
输出数据只有一个整数（计算结果四舍五入），表示计算出的最小平均等待时间。
示例输入：
10 2
56 12 1 99 1000 234 33 55 99 812示例输出：
336提示：
参考答案（内存最优[1092]）：
#include<stdio.h>
#define Max 0x7fffffff
int main()
{
int A[10000],B[1000]={0};
int n,s,x,min=Max;
int i,j,t=0;
scanf("%d%d",&n,&s);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
for(i=0;i<n;i++)
for(j=i;j>=1;j--)
if(A[j]<A[j-1])
{
x=A[j];
A[j]=A[j-1];
A[j-1]=x;
}
for(i=0;i<n;i++)
{
for(j=0;j<s;j++)
if(B[j]<min)
{
min=B[j];
x=j;
}
B[x]=B[x]+A[i];
t=t+B[x];
min=Max;
}
double y=(double)t/n;
y=(y-t/n)*10;
if(y>=5)
printf("%d",t/n+1);
else
printf("%d",t/n);
return 0;
}
参考答案（时间最优[0]）：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int a[10001];
int svs[1001];
int sum[1001];
int main()
{
int n,s;
scanf("%d%d",&n,&s);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int i=0;
int j=0;
while(i<n){
svs[j]+=a[i];
sum[j]+=svs[j];
i++,j++;
if(j==s) j=0;
}
double t=0;
for(int i=0;i<n;i++) t+=sum[i];
int ans = int(t/n+0.5);
printf("%d\n",ans);
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。