HDU1053_田忌赛马

题目大意:         田忌赛马,每输赢一局的赌注为200,n为一方的马数量(双方马一样多),且最大为1000. 解题思路:         具体解题思路如下:(这段思路是看别人的)                       1.当田忌最慢的马比齐王最慢的马快,赢一场先。因为始终要赢齐王最慢的马,不如用最没用的马来赢它。                       2.当田忌最慢的马比齐王最慢的马慢,和齐王最快的马比,输一场。因为田忌最慢的马始终要输的,不如用它来消耗齐王最有用的马。                       3.当田忌最慢的和齐王最慢的马慢相等时,分4和5讨论。                       4.当田忌最快的马比齐王最快的马快时,赢一场先。因为最快的马的用途就是来赢别人快的马,别人慢的马什么马都能赢。                       5.当田忌最快的马比齐王最快的马慢时,拿最慢的马和齐王最快的马比,输一场,因为反正要输一场,不如拿最没用的马输。                       6.当田忌最快的马和齐王最快的马相等时,这就要展开讨论了,贪心方法是,拿最慢的马来和齐王最快的马比。                自己想不出贪心的思路,最后还是看的别人的分析,理解后才把代码给敲出来的~~~更悲剧的是知道思路了,还把代码写错了,一开始用了一个for循环,忘了一种情况,田忌的低速马是不增加的,所以,最好是用while.                设置tian_slow,tian_fast,king_slow,king_fast来表示双方的马的好坏。 代码:
#include
#include
#include
using namespace std;
const int MAX = 1005;
int main(void)
{
	int n;
	int tian[MAX], king[MAX];
	while(scanf("%d", &n), n)
	{
		for(int i=0; i king[king_slow])
			{
				tian_slow++;
				king_slow++;
				result++;
			}
			else
			{
				if(tian[tian_fast] > king[king_fast])
				{
					result++;
					tian_fast--; king_fast--;
				}
				else if(tian[tian_fast] < king[king_fast])
				{
					result--;
					tian_slow++;
					king_fast--;
				}
				else
				{
					if(tian[tian_slow] < king[king_fast])
					{
						result--;
						tian_slow++;
						king_fast--;
					}
					else
					{
						break;//剩下的均相等
					}
				}
			}
		}
		printf("%d\n", result*200);
	}
	return 0;
}
原文地址:https://www.cnblogs.com/cchun/p/2520207.html