多处最优服务次序问题

多处最优服务次序问题

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注