博客

贪心策略：

1，如果田忌的最快马快于齐王的最快马，则两者比。

（因为若是田忌的别的马很可能就赢不了了，所以两者比）

2，如果田忌的最快马不快于齐王的最快马，则比较田忌的最慢马和齐王的最慢马

2.1，若田忌最慢马快于齐王最慢马，两者比。（田忌的最慢马既然能赢一个就赢呗，而且齐王的最慢马肯定也得有个和他比，所以选最小的比他快得。）

2.2，其他，则拿田忌的最慢马和齐王的最快马比。

（反正所有的马都比田忌的最慢马快了，所以这匹马必输，选贡献最大的，干掉齐王的最快马）

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

int count1=0;//胜利场次 
int count2=0;//平局场次 
int cnt=0;//败北场次 

int tianRac(vector<long long>Tian, vector<long long>King, int n)
{
	int money = 0; // 田忌赢的钱
	int tianh = 0, tiane = n-1, kingh = 0, kinge = n-1;
	// 分别标记田忌马队和齐王马队的最快和最慢的马
	// 共有 n 次比赛，每进行一次，就换下一匹马
	for (int i = 0; i < n; i++){
	// 田忌快马比齐王快马快时，那就和他一较高下
		if (Tian[tianh] > King[kingh]){
			count1++; 
			tianh++;// 下一个
			kingh++;// 下一个
		}
	// 田忌快马不比齐王快马快时，比较慢马是否能赢 
		else {
			// 田忌的慢马比齐王的慢马快时
			if (Tian[tiane] > King[kinge]) {
				count1++; 
				tiane--;
				kinge--;
			}
			// 田忌的慢马不比齐王的慢马快，就用慢马和他快马比
			else if (Tian[tiane] > King[kingh]) {
				cnt++;
				tiane--;
				kingh++;
			}
		}
	}
	count2=n-count1-cnt; 
	money=count1*200-cnt*200;
	return money;	//返回田忌赢的钱
}
int main()
{
	int n;// 比赛双方马的数量
	cout << "公等马几何" << endl;
	cin >> n;
	vector <long long> tian;
	vector <long long> king;
	long long x;
	cout << "将军 马之疾" << endl;
	for (int i = 0; i < n; i++){
		cin >> x ;
		tian.push_back(x);
	}
	cout << "王 马之疾" << endl;
	for (int i = 0; i < n; i++){
		cin >> x ;
		king.push_back(x);
	}
	// 降序排xu
	sort(tian.begin(),tian.end(),greater<long long>());
	sort(king.begin(),king.end(),greater<long long>());
	int result = tianRac(tian, king, n);
	if(result > 0){
		cout << "将军 胜" << result << "两" << endl;
	}
	else if (result == 0){
		cout << "和" << endl;
	}
	else{
		cout << "将军 输" << -result << "两" << endl;
	}
	return 0;
}