算法实现题4-6最优服务次序问题

本文主要是介绍算法实现题4-6最优服务次序问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

4-6 最优服务次序问题

问题描述：设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti(1≤i≤n)。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。

算法设计：对于给定的n个顾客需要的服务时间，计算最优服务次序。

数据输入：第1行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。

输入样例：

10
56 12 1 99 1000 234 33 55 99 812

结果输出：输出最小平均等待时间

输出样例：

532.00

贪心策略：

需要服务时间短的顾客先接受服务的。

注意：总的等待时间是所有顾客等待时间之和并且每位顾客的等待时间包括自己所需要的时间

AC码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,sum=0;
	cin >> n;
	double ave;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin >> a[i];	
	} 
	sort(a,a+n);
	for(int i=0;i<n;i++)
	{
		sum=sum+a[i]*(n-i);	
	} 
	/*
	for(int i=1;i<n;i++)
	{
		a[i]=a[i]+a[i-1];       // 第i+1个顾客等待时间应该是第i个顾客等待时间+第i+1个顾客花费的时间a[i+1]
	}	
	for(int i=0;i<n;i++)
	{
		sum=sum+a[i];
	}
	*/
	ave=sum*1.0/n;
	printf("%.2f",ave);
	return 0;	
}

这篇关于算法实现题4-6最优服务次序问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！