程式基本算法習題解析 最優服務次序問題

題目：

最優服務次序問題：設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti,1<=i<=n。應如何安排n個顧客的服務次序，才能使平均等待時間最少？平均等待時間是n個顧客等待服務時間的總和除以n。

思路：

先服務等待時間最少的顧客，是以首先需要對顧客需要的服務時間進行排序，且每個顧客的等待時間除了自身需要的服務時間外，還需加上自己開始被服務前的等待時間（比自己的服務時間短的顧客的服務時間總和），最後對每個顧客的等待加服務時間進行求和求平均，即為最短平均等待時間。

附上代碼：

// Chapter9_3.cpp : Defines the entry point for the application.
// 最優服務次序問題：設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti,1<=i<=n。
// 應如何安排n個顧客的服務次序，才能使平均等待時間最少？
// 平均等待時間是n個顧客等待服務時間的總和除以n。

#include "stdafx.h"
#include<iostream>
using namespace std;

//排序
//從小到大，參數為：數組，數組個數
void funSort(int *a,int n)
{
	int temp;
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
}
int minWaitingTime(int *a,int n) //數組a為顧客的服務時間
{
	int *b = new int[n];
	int i,sum=0;
	for(i=0;i<n;i++)
		b[i] = a[i];
	//最終的b[i]為第i位顧客等待的時間
	for(i=1;i<n;i++)
		b[i] = b[i]+b[i-1];
	//求顧客等待時間的總和
	for(i=0;i<n;i++)
		sum += b[i];
	delete []b;
	return sum/n; //傳回平均等待時間
}
int main()
{
	int N,i,aveTime; //N:顧客總數,aveTime:p最少平均等待時間
	cout << "input the number of the customer: ";
	cin >> N;
	int *time = new int[N]; //使用者輸入的各顧客的服務時間
	cout << "input the need service time of each customer: " << endl;
	for(i=0;i<N;i++)
	{
		cout << "No" << i+1 << ": ";
		cin >> time[i];
	}
	funSort(time,N);

	cout << "排序後的數組為： ";
	for(i=0;i<N;i++)
		cout << time[i] << ' ';
	cout << endl;
	aveTime = minWaitingTime(time,N);
	cout << "the least average waiting time is: " << aveTime << endl;
	delete []time;
	system("pause");
	return 0;
}
           

運作結果為：

另外，也可以用vector代替數組，避免了動态配置設定記憶體，程式如下：

#include "stdafx.h"
#include<iostream>
#include<vector> 
using namespace std;

void funSort(vector<int>&a)
{
	int temp,n;
	n = a.end()-a.begin();
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
}
int minWaitingTime(vector<int>a) //數組a為顧客的服務時間
{
	vector<int>b;
	int i,n,sum=0;
	n = a.end()-a.begin();
	for(i=0;i<n;i++)
		b.push_back(a[i]);
	//最終的b[i]為第i位顧客等待的時間
	for(i=1;i<n;i++)
		b[i] = b[i]+b[i-1];
	//求顧客等待時間的總和
	for(i=0;i<n;i++)
		sum += b[i];
	return sum/n; //傳回平均等待時間
}
int main()
{
	int N,i,aveTime,temp; //顧客總數
	vector<int>time; 
	cout << "input the number of the customer: ";
	cin >> N;
	cout << "input the need service time of each customer: " << endl;
	for(i=0;i<N;i++)
	{
		cout << "No" << i+1 << ": ";
		cin >> temp;
		time.push_back(temp);
	}
	funSort(time);
	aveTime = minWaitingTime(time);
	cout << "the least average waiting time is: " << aveTime << endl;
	system("pause");
	return 0;
}
           

 運作結果和之前一樣。