洛谷 P1650 田忌賽馬 Ac代碼 (簡單的 “桶排序”)

田忌賽馬 - 洛谷

https://www.luogu.com.cn/problem/P1650

題目描述

我國曆史上有個著名的故事： 那是在2300年以前。齊國的大将軍田忌喜歡賽馬。他經常和齊王賽馬。他和齊王都有三匹馬：正常馬，上級馬，超級馬。一共賽三局，每局的勝者可以從負者這裡取得200銀币。每匹馬隻能用一次。齊王的馬好，同等級的馬，齊王的總是比田忌的要好一點。于是每次和齊王賽馬，田忌總會輸600銀币。

田忌很沮喪，直到他遇到了著名的軍師――孫膑。田忌采用了孫膑的計策之後，三場比賽下來，輕松而優雅地赢了齊王200銀币。這實在是個很簡單的計策。由于齊王總是先出最好的馬，再出次好的，是以田忌用正常馬對齊王的超級馬，用自己的超級馬對齊王的上級馬，用自己的上級馬對齊王的正常馬，以兩勝一負的戰績赢得200銀币。實在很簡單。

如果不止三匹馬怎麼辦？這個問題很顯然可以轉化成一個二分圖最佳比對的問題。把田忌的馬放左邊，把齊王的馬放右邊。田忌的馬A和齊王的B之間，如果田忌的馬勝，則連一條權為200的邊；如果平局，則連一條權為0的邊；如果輸，則連一條權為－200的邊……如果你不會求最佳比對，用最小費用最大流也可以啊。 然而，賽馬問題是一種特殊的二分圖最佳比對的問題，上面的算法過于先進了，簡直是殺雞用牛刀。現在，就請你設計一個簡單的算法解決這個問題。

輸入格式

第一行一個整數n，表示他們各有幾匹馬（兩人擁有的馬的數目相同）。第二行n個整數，每個整數都代表田忌的某匹馬的速度值(0 <= 速度值<= 100)。第三行n個整數，描述齊王的馬的速度值。兩馬相遇，根據速度值的大小就可以知道哪匹馬會勝出。如果速度值相同，則和局，誰也不拿錢。

輸出格式

僅一行，一個整數，表示田忌最大能得到多少銀币。

這是一道洛谷上道綠題（難度：普及+/提高） 

但是！

它是一道非常簡單的 “桶排序 ”

但是有很多人被它誤導成為 “貪心”“Dp”

下面講講桶排做法:

1、設定兩個數組，分别代表代表田忌和齊王的馬

1.1 數組上的數字代表每匹馬的速度

1.2 數組中存放的數字代表馬的數量

eg. x[100]=50：有 50 匹速度為 100 的馬

2、輸入與存入

2.1 分别輸入n匹速度為c的馬并把它們按速度存入相應的數組

3、算田忌最多能赢齊王多少次

3.1 優先算勝場（可以賺錢） 

4、算平局

4.1 排除剩下的平局的情況 

5、算敗局

5.1 存放“田忌的馬”的數組裡剩下的的數，都是戰敗馬

5.2 減掉敗場的馬所輸的錢數

兩種馬的數量比較：

取目前兩種馬數量的最小值

兩種馬分别減去這個最小值

（總有一種馬的數量歸為0） 

判斷總錢數是否變化 

注釋代碼：

#include<iostream>
using namespace std;

const int N=110;			//設定桶的大小 
int a[N],b[N];				//設定兩個大小為 100 的桶，a桶代表田忌的馬，b桶代表齊王的馬 
int n,ans;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int c;
		scanf("%d",&c);
		a[c]++;				//田忌的馬 
	}
	for(int i=1;i<=n;i++){
		int c;
		scanf("%d",&c);
		b[c]++;				//齊王的馬 
	}
	
	for(int o=1;o<100;o++){	//算勝場，o表示的量為田忌對戰齊王的馬的速度差距 
	//注：差距越小，占利越高（每匹馬速度差距不會太的，但又要保證能勝對方） 
		for(int i=100;i>o;i--){			//i表示目前比較時田忌的馬的速度 
			if(a[i]==0) continue;		//若目前速度的馬匹為 0，則跳過本輪 
			int k=min(a[i],b[i-o]);		//求兩種馬匹的最小值（o表速度差） 
			a[i]-=k , b[i-o]-=k , ans+=200*k ;	//減去最小值，總錢數增加 
		}
	}
	
	for(int i=1;i<100;i++){						//求兩種馬平局的數量 
		if( a[i]==0 || b[i]==0 ) continue;
		int k=min(a[i],b[i]);					//減去所有平局的情況 
		a[i]-=k , b[i]-=k ;
	}
	
	for(int i=1;i<100;i++){
		if(a[i]) ans-=a[i]*200;					//求敗場，總錢數減少 
	} 
	
	printf("%d",ans);
	return 0;
}  
           

原代碼（減縮）：

#include<iostream>
using namespace std;
const int N=101;
int a[N],b[N],n,c,k,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&c);
		a[c]++ ;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&c);
		b[c]++ ;
	}
	for(int o=1;o<100;o++){
		for(int i=100;i>o;i--){
			if(!a[i]) continue;
			k=min(a[i],b[i-o]);
			a[i]-=k , b[i-o]-=k , ans+=200*k ;
		}
	}
	for(int i=1;i<100;i++){
		if(!a[i]||!b[i]) continue;
		k=min(a[i],b[i]);
		a[i]-=k , b[i]-=k ;
	}
	for(int i=1;i<100;i++) if(a[i]) ans-=a[i]*200 ;
	printf("%d",ans);
	return 0;
}