一、會場安排問題

1.1 問題描述

?假設(shè)在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計一個有效的貪心算法進行安排。

數(shù)據(jù)輸入：
第 $1$ 行中有一個整數(shù) $n$，表示有 $n$ 個待安排的活動。接下來的 $n$ 行中，每行有 $2$ 個正整數(shù)，分別表示 $n$ 個待安排的活動的開始時間和結(jié)束時間。時間以 $0$ 點開始的分鐘計。
數(shù)據(jù)輸出：
計算出的最少會場數(shù)并輸出。

1.2 思路分析

?1. 貪心策略：采用結(jié)束時間最早的會場作為貪心選擇。

?2. 用數(shù)組 $s$ 和 $f$ 分別存儲各活動的開始時間和結(jié)束時間。

• 將數(shù)組 $s$ 排序，該次序為各活動選擇會場的次序。
• 將數(shù)組 $f$ 排序。由于會場的結(jié)束時間由活動的結(jié)束時間決定，排序后的數(shù)組也是會場的結(jié)束時間點。

?3. （1）先為最早開始的活動開辟一個會場，此時會場的最早結(jié)束時間為該活動的結(jié)束時間。（2）然后遍歷剩下的活動。對于每個活動，判斷當(dāng)前最早結(jié)束的會場內(nèi)是否仍有活動：如果有，開辟一個新會場；如果沒有，說明當(dāng)前最早結(jié)束的會場能容納當(dāng)前的活動，更新會場的結(jié)束時間點，保證最早結(jié)束的會場最先開始下一個活動。

1.3 例題分析

?設(shè)有 $4$ 個活動，每個活動的開始和結(jié)束時間分別為 {1, 6}，{4, 8}，{9, 10}，{7, 18}。

可能有同學(xué)有疑惑：每個活動的開始時間和結(jié)束時間怎么是分開排序的？那每個活動的開始時間和結(jié)束時間關(guān)聯(lián)性不是打破了嗎？有關(guān)聯(lián)性的東西怎么能排序？
答： 這道題不用關(guān)聯(lián)，這個解法，只需要關(guān)心開始時間和結(jié)束時間，，只要集合里面的最大結(jié)束時間和當(dāng)前的開始時間就可以。

1.4 代碼編寫

樣例輸入：
5
1 23
12 28
25 35
27 80
36 50
樣例輸出：
3

時間復(fù)雜度為 $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cout<<"請輸入活動的個數(shù)："<<endl;
	cin>>n;
	
	int s[n],f[n];
	cout<<"請輸入每個活動的開始時間和結(jié)束時間："<<endl;
	for(int i=0;i<n;i++)
	{
		cin>>s[i]>>f[i];
	}
	
	sort(s,s+n);//理解一下為什么都要升序 
	sort(f,f+n);
	
	//會場的最短結(jié)束時間次序用j來表示，待分配的活動按i來遍歷 
	int j=0,ans=0;
	
	for(int i=0;i<n;i++)
	{
		if(s[i] < f[j])
		{
			ans++;
		}
		else
		{
			j++;
		}
	} 
     
	cout<<"最小會場數(shù)是："<<ans<<endl; 
	return 0;
}

二、最優(yōu)服務(wù)次序問題

2.1 問題描述

?設(shè)有 $n$ 個顧客同時等待一項服務(wù)。顧客 $i$ 需要的服務(wù)時間為 $t_i$，$1\le i\le n$。應(yīng)如何安排 $n$ 個顧客的服務(wù)次序才能使平均等待時間達到最小? 平均等待時間是 $n$ 個顧客等待服務(wù)時間的總和除以 $n$。對于給定的 $n$ 個顧客需要的服務(wù)時間，編程計算最優(yōu)服務(wù)次序。

數(shù)據(jù)輸入：
第 $1$ 行是正整數(shù) $n$，表示有 $n$ 個顧客。接下來的 $1$ 行中，有 $n$ 個正整數(shù)，表示 $n$ 個顧客需要的服務(wù)時間。
數(shù)據(jù)輸出：
輸出對應(yīng)的最小平均等待時間，保留 $2$ 位小數(shù)。

2.2 思路分析

?貪心策略：服務(wù)時間較短的顧客先完成他的業(yè)務(wù)，就會使總的等待時間達到最短。

2.3 代碼編寫

樣例輸入：
10
56 12 1 99 1000 234 33 55 99 812
樣例輸出：
532.00

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cout<<"請輸入顧客的數(shù)目："<<endl;
	cin>>n;
	
	int a[n];
	cout<<"請輸入每位顧客需要服務(wù)的時間："<<endl; 
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	sort(a,a+n);  //將每位顧客的等待時間按升序排序 
	
	int sum=0;
	int num=n;  //還剩下num個人在同時等當(dāng)前這個在辦理業(yè)務(wù)的人
	for(int i=0;i<n;i++)
	{
		sum = sum+num*a[i]; //接受服務(wù)的那個人其實也在等待自己的服務(wù)結(jié)束 
		num--;
	}

    cout<<"平均等待時間是："<<endl;
    double ans=sum/n;
	cout<<fixed<<setprecision(2)<<ans<<endl;
	return 0; 
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-781323.html

到了這里，關(guān)于計算機算法分析與設(shè)計（14）---貪心算法(會場安排問題和最優(yōu)服務(wù)次序問題)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！