题目描述
设有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
参考代码
//a
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a, const void *b)
{
return *(int *)a- *(int *)b;
}
int a[10005];
int time[1005];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++)
scanf("%d", &a[i]);
qsort(a, n+1, 4, cmp);
int j=1;
int sum[10005];
for (int i=1; i<=n; i++)
{
if(j==m+1)
j=1;
time[j]+=a[i];
sum[j]+=time[j];
j++;
}
double ans=0;
for (int i=1; i<=m;i++)
{
ans+=sum[i];
}
ans=(ans/(n));
if(ans-(int)ans>=0.5)
ans=ans+1;
printf("%d", (int)ans);
return 0;
}
解析
暂无