实验——田忌赛马c++

故事概述：
孙膑先以下等马对齐威王的上等马，第一局田忌输了。接着进行第二场比赛。孙膑拿上等马对齐威王的中等马，获胜了一局。 第三局比赛，孙膑拿中等马对齐威王的下等马，又战胜了一局。 比赛的结果是三局两胜，田忌赢了齐威王。 还是同样的马匹，由于调换一下比赛的出场顺序，就得到转败为胜的结果。

问题描述：
如果3匹马变成n匹（n<=100），齐王仍然让他的马按照优到劣的顺序初赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子；输一局，田忌就要输掉200两银子。已知道国王和田忌的所有马的奔跑速度，并且所有马的奔跑速度均不相同，现已经对两人的马分别从快到慢排好序。请设计一个算法，帮助田忌赢得最多的银子。
要求：
输入：第一行一个整数n，表示双方各有n匹马；
第二行n个整数分别表示田忌的n匹马的速度；
第三行n个整数分别表示齐王的n匹马的速度。
输出：若通过聪明的你精心安排，如果能赢得比赛（赢的次数大于比赛总次数的一半），那么输出“YES”。 否则输出“NO”。并输出一个整数，代表田忌最多能赢多少两黄金。
分析：

贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解

• 如果田忌最快的马比齐王最快的马快，则比之

• 如果田忌最快的马比齐王最快的马慢，则用田最慢的马跟齐最快的马比 //这是贪心的第一步

• 如果田忌最快的马的速度与齐威王最快的马速度相等

  • 如果田忌最慢的比齐威王最慢的快，则比之
    //这是贪心的第二步
  • 如果田忌最慢的比齐威王最慢的慢，田忌慢VS齐王快
  • 田忌最慢的与齐威王最慢的相等，田忌慢VS齐王快

  代码（C++）：

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int a[maxn];      //田忌的马的速度
int b[maxn];	 //齐王的马的速度
bool cmp(const int &a, const int &b) {             //先将田忌跟齐王的马的速度数组进行一次冒泡排序
	return a>b;
}

int main() {
	int n;       //双方各有的马匹数（同为n）
	while (cin >> n && n) {
		for (int i = 1; i <= n; i++)       //数组赋值
			cin >> a[i];
		for (int i = 1; i <= n; i++)			//数组赋值
			cin >> b[i];
		sort(a + 1, a + n + 1, cmp);
		sort(b + 1, b + n + 1, cmp);
		int sa = 1, ea = n;
		int sb = 1, eb = n;
		int ans = 0;
		while (sa <= ea && sb <= eb) {
			if (a[sa]>b[sb]) {
				ans++;
				sa++;
				sb++;
			}
			else if (a[sa]<b[sb]) {
				ans--;
				ea--;
				sb++;
			}
			else {
				if (a[ea]>b[eb]) {
					ans++;
					ea--;
					eb--;
				}
				else if (a[ea]<b[eb]) {
					ans--;
					ea--;
					sb++;
				}
				else {
					if (a[ea]<b[sb]) {
						ans--;
					}
					ea--;
					sb++;
				}
			}

		}

		if (ans>0)
		{
			cout << "YES" << endl;
			cout << "田忌赢了" << endl;
			cout << "获得了" << ans * 200 << "银两" << endl;
		}

		else if (ans<0)
		{
			cout << "NO" << endl;
			cout << "田忌输了" << endl;
			cout << "输了" << ans * 200 << "银两" << endl;
		}
		else
			cout << "田忌与齐王打平" << endl;
	}
	return 0;
}