题目描述

中国古代一个有名的故事 ” 田忌赛马” 。 田忌和齐王赛马， 他们各有 n 匹马，依次派出一匹马进行比赛， 每一轮获胜的一方将从输的一方获得 200 银币， 平局则不用出钱。其中每匹马只能出场一次，每匹马有一个速度值，在比赛中速度快的马一定会获胜。田忌知道所有马的速度值，且田忌可以安排每轮双方出场的马。问田忌如何安排马的出场顺序，使得最后获得的钱最多？

输入

输入包含若干组数组， 每个数据的第 1 行是一个整数 n (n≤1000)，表示齐王和田忌各有 n 匹马， 后面的两行每行有 n 个数，分别表示田忌 n 匹马和齐王 n 匹马的速度值。测试数据以 0 结束。

输出

输出有若干行，每行输出对应一组输入。输出是一个整数，表示田忌最多获得的钱数 （损失钱则用负数表示）。

输入输出样例

样例输入 #1

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

样例输出 #1

200
0
0

 一、题目分析：田忌赛马是一种权衡取舍，找适合策略，来收获最大利益的问题。在本题中我们先将田忌与齐王的马进行排序（在此，我以降序排序），然后选择最优解（比较快马）：

1、田忌>齐王：正常比赛。

2、田忌<齐王：田忌慢马与齐王快马比赛。以慢换快

3、田忌=齐王（这一点十分容易忽略）：这时我们可以观察慢马，若此时田忌>齐王，可以直接让慢马比赛（无疑时必赢的）。若此时田忌<=齐王，将田忌慢马与齐王快马比赛（与慢马或快马进行比赛，都是不可能赢的，何不换取更大的利益）。

二、c++代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1001;
int arr1[MAXN], arr2[MAXN];
bool cmp2(int x, int y) {
	return x > y;
}
int main() {
	int n;
	while (cin >> n) {
		if (n == 0) return 0;  //终止条件
		for (int i = 0; i < n; i++) cin >> arr1[i];
		for (int j = 0; j < n; j++) cin >> arr2[j];
		sort(arr1, arr1 + n, cmp2),sort(arr2, arr2 + n, cmp2); //sort从快到慢排序
		int left_1 = 0, left_2 = 0,sum=0;  //标记左侧快马序数
		int right_1 = n - 1, right_2 = n - 1;//标记右侧慢马序数
		for (int i = 0; i < n; i++) {
			if (arr1[left_1] > arr2[left_2]) left_1++,left_2++,sum++; //快马：田忌>齐王
			else if (arr1[left_1] < arr2[left_2]) right_1--,left_2++,sum--; //快马：田忌<齐王
			else if (arr1[right_1] > arr2[right_2]) right_1--,right_2--,sum++;  //快马（田忌=齐王），比较慢马：田忌>齐王
			else if (arr1[right_1] < arr2[left_2]) right_1--,left_2++,sum--;    //快马（田忌=齐王），比较慢马：田忌<=齐王
		}
		cout << sum * 200 << endl;
	}
}