学步园

题目大意：田忌的马一定得比齐王的马快才能赢，问n次比赛结束后田忌最多能赢多少钱！（注意：并不是同一等级的马齐王一定比田忌快）;

解题思路：贪心.

贪心的策略：

一、当田忌最快的马比国王最快的马快时，用田忌最快的马赢国王最快的马。 
二、当田忌最快的马比国王最快的马慢时，用田忌最慢的马输给国王最快的马。
三、当田忌最快的马跟国王最快的马一样快时，分情况。

所以：对于情况三，我们应该从最慢的马开始考虑了

1、当田忌最慢的马比国王最慢的马快，那么用田忌最慢的马赢国王最慢的马

2、当田忌最慢的马比国王最慢的马慢，那么用田忌最慢的马输给国王最快的马

3、当田忌最慢的马跟国王最慢的马相等的时候，用田忌最慢的马跟国王最快的马比

倒过来思考也是一样的。。。

代码如下：

/*
 * 1052_3.cpp
 *
 *  Created on: 2013年8月10日
 *      Author: Administrator
 */

#include <iostream>
#include <algorithm>

bool compare(int a, int b) {
	return a < b;
}
using namespace std;
int main() {
	int n;
	while (scanf("%d", &n) != EOF, n) {
		int a[n], b[n];
		int i, j;
		for (i = 0; i < n; ++i) {
			scanf("%d", &a[i]);
		}

		for (i = 0; i < n; ++i) {
			scanf("%d", &b[i]);
		}
		sort(a, a + n);
		sort(b, b + n);

		int win = 0, kn = n;

		for (i = 0, j = 0; i < n;) {
			if (a[i] > b[j]) {
//				printf("a[%d]=%d,b[%d]=%d\n",i,a[i],j,b[j]);
//				cout<<"1"<<endl;
				win++;
				++i;
				++j;
			} else if (a[i] < b[j]) {
//				cout<<"2"<<endl;
				--win;
				++i;
				--kn;
			} else {
//				cout<<"3"<<endl;
				if (a[n - 1] > b[kn - 1]) {
//					cout<<"3_1"<<endl;
					++win;
					--n;
					--kn;
				} else if (a[n - 1] < b[kn - 1]) {
//					cout<<"3_2"<<endl;
					--win;
					++i;
					--kn;
				} else if (a[n - 1] == b[kn - 1]) {
//					cout<<"3_3"<<endl;
					if (a[i] < b[kn - 1]) {
						--win;
					}

					++i;
					--kn;
				}
			}
		}

		printf("%d\n", win * 200);
	}
}

以上附上另外一篇博客的地址。算法都是一样的。但他的代码有注释。在这里我就懒得写注释了。。

http://blog.csdn.net/jjike/article/details/8571489