洛谷 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;
}