学步园

HDOJ1052田忌赛马题目描述

这道题是一道以田忌赛马为背景的题目，题目中有说道可以用二分匹配来做，可惜俺只知道二分图，不知道什么是二分匹配，所以就用贪心来做咯，这道题是一道挺好的贪心题目。

下面直接看代码，分析都在代码里面

/*
HDOJ1052
田忌赛马
先将田忌和齐王的马都按速度降序排序，然后开始比
贪心：要赢就要以最小的差距赢，输就要以最大的差距去输，就是要用对自己的影响最小的去输和赢
1、田忌最快的 > 齐王最快的 直接比
2、田忌最快的 < 齐王最快的 用田忌最慢的和齐王最快的比 (对自己接下来的比赛影响最小)
3、田忌最快的 = 齐王最快的 这时候要分下面集中情况
	3.1、田忌最慢的 > 齐王最慢的 用最慢比最慢
	3.2、田忌最慢的 < 齐王最慢的 用最慢比最快
	3.3、田忌最慢的 = 齐王最慢的 这时候再分两种情况
		3.3.1、田忌最慢和齐王最快一样，这时候从田忌的最快到最慢都是和齐王一样的，直接跳出，给最后结果
		3.3.2、田忌最慢比齐王最快慢 用最慢比最快

*/
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(int a,int b)
{
	return (a>b); //按照速度降序排序
}

int main()
{
	int tian[1000],king[1000];
	int win,n,i;
	int th,tt; //th田忌最快的马,tt田忌最慢的马
	int kh,kt; //kh齐王最快的马,kt齐王最慢的马

	while(cin>>n && n)
	{
		for(i=0;i<n;i++)
			cin>>tian[i];
		sort(tian,tian+n,cmp);
		
		for(i=0;i<n;i++)
			cin>>king[i];
		sort(king,king+n,cmp);

		win=0;
		th=kh=0;
		tt=kt=n-1;
		while(th<=tt)
		{
			if(tian[th] > king[kh]) //case 1
			{
				th++;
				kh++;
				win++;
			}
			else if(tian[th] < king[kh]) //case 2
			{
				tt--;
				kh++;
				win--;
			}
			else	//case 3
			{
				if(tian[tt] > king[kt]) //case 3.1
				{
					tt--;
					kt--;
					win++;
				}
				else if(tian[tt] < king[kt]) //case 3.2
				{
					tt--;
					kh++;
					win--;
				}
				else	//case 3.3
				{
					if(tian[tt] == king[kh])  //case 3.3.1
						break;
					else        //case 3.3.2
					{
						tt--;
						kh++;
						win--;
					}
				}
			}
		}
		cout<<win*200<<endl;
	}
	return 0;
}

贪心是要求最优解，这道题就是要求田忌最多可以赢多少钱，那么贪心的话，就是要尽量保存自己快的马去赢，让自己慢的马去输。每次都是在做出贪心选择之后，再解决子问题，所以是符合贪心选择性质的，所以可以保证用贪心来做是可以得出最优解的。