POJ2287 田忌赛马---贪心算法

田忌赛马

题目详见http://poj.org/problem?id=2287
	田忌赛马大家都听过，可是如果不是上中下三等马，而是很多匹马，优劣有很多种分类，就不仅仅是321的问题了。
	这个很明显就是贪心算法，贪心算法的宗旨就是一个字------贪！有最小的代价换取最大的利益，我们都很喜欢。田忌当年请教孙膑的时候，孙膑对田忌说：“现在用您的下等马对付齐王的上等马，拿您的中等马对付齐王的下等马，拿您的上等马对付齐王的中等马。”赢一局赢200金，输一局输200金，平局没钱。
	总体的思想就是田忌以最小代价赢齐王，最小代价输齐王！ 齐王以最大代价赢田忌，最大代价输田忌！
	所以我们先把所有种类马按速度从高到低排序，这样就知道了快马在前，慢马在后。我们接下来所说的快马就是当前没有参加比赛的最快马，慢马就是当前没有参加比赛的最慢马。我们按孙膑的思路走。我们从最慢马开始比较，这样直接用自己的最慢马换取胜利，或者是最小代价的输，这次是贪心的本质啊。  

	如果田忌的慢马比齐王的慢马快，那肯定要比赛，因为是必赢的，我干嘛不比，这是最小的价值获取的胜利啊！如果田忌的慢马比齐王的慢马慢呢？无论怎么比赛，和哪个马去比赛，这马必输，是炮灰的死棋。死也要拉个好的垫背，用它去和齐王最快的马比赛，输的不亏！如果田忌的慢马的速度等于齐王的慢马呢？这个时候我们说不准，我们去比较双方的快马，如果此时田忌的快马比齐王的快马快，那直接比赛，因为是必赢！如果田忌的快马比齐王的快马慢呢呢？如果田忌的快马的速度等于齐王的快马呢？这个时候给他一个最慢的马不就行了嘛，最小的代价换取对方的一个快马不好吗？或许你会说如果相等不就可以平局了吗，不输了至少。可是你忘了贪心是干嘛的了？要贪！再说了，田忌这个最慢的马都跑不过齐王的最慢马，和炮灰有啥区别！如果你说让两个慢马去比赛，平局，可是如果田忌的快马比不过齐王的快马呢？那不是输一局？让最慢的马去吃掉齐王最快的马，至少是不吃亏的。不过要注意一点，去让这个慢马当炮灰的时候要注意一点，那就是如果这个慢马和齐王的快马速度一样，或者更大，那就不是炮灰了。此时的情况就是剩余的马速度都是一样的了。因为刚才比较的时候双方的慢马速度一样，快马速度一样，这个时候你说田忌的慢马不输齐王的快马，那不就是剩余的马速度都一样了嘛！再比较下去就没啥意思了。N场比赛，平局的就不管了，我们只关注输赢的场次。  


总结：1 如果田忌的慢马比齐王的慢马快，直接比赛。赢的代价小！
      2 如果田忌的慢马比齐王的慢马慢，让他和齐王的快马比赛。输的值！
      3 如果田忌的慢马的速度等于齐王的慢马
 	   1 如果田忌的快马比齐王的快马快 ，直接比赛。赢！
	   2 如果田忌的慢马比齐王的快马慢，那让他和齐王最快的马比赛。输的值！
           3 其他情况，直接退出。统计比赛结果，算钱！
上代码，这个代码在POJ上AC了，在HDOJ上是RE，我很纠结啊。难道和容器有关系?先不管了。  
#include<iostream>  
#include<algorithm> 
#include<vector>
using namespace std;
bool MaxToMin(const int& a ,const int& b);

int main()
{	
	int n,n1,n2;
	int i,j,k;
	int speed;
	int WinTimes,LoseTimes,money;
	vector<int> TianHorse;
	vector<int> KingHorse;
	while(cin>>n)
	{
		if(0==n)
			break;
		money=WinTimes=LoseTimes=0;
		n1=n2=n-1;
		TianHorse.clear();
		KingHorse.clear();
		for(i=0;i<n;i++)
		{
			cin>>speed;
			TianHorse.push_back(speed);
		}
		for(i=0;i<n;i++)
		{
			cin>>speed;
			KingHorse.push_back(speed);
		}
		sort(TianHorse.begin(),TianHorse.end(),MaxToMin);
		sort(KingHorse.begin(),KingHorse.end(),MaxToMin);
		i=j=0;
		for(k=0;k<n;k++)
		{
			if(TianHorse[n1]>KingHorse[n2])
			{
				n1--;
				n2--;
				WinTimes++;
			}
			else if(TianHorse[n1]<KingHorse[n2])
			{
				LoseTimes++;
				n1--;
				j++;
			}
			else
			{
				if(TianHorse[i]>KingHorse[j])
				{
					WinTimes++;
					i++;
					j++;
				}
				else if(TianHorse[n1]<KingHorse[j])
				{
					LoseTimes++;
					n1--;	
					j++;
				}
				else
					break;
			}
		}
		money=(WinTimes-LoseTimes)*200;
		cout<<money<<endl;
	}
	return 0;
}
bool MaxToMin(const int& a ,const int& b)
{
	if (a>=b) 
		return true;
	else
		return false;
}
这个好像也可以用DP来做
转载请注明出处http://blog.csdn.net/liangbopirates/article/details/10035865