【 OJ 】 HDOJ1052 贪心模拟田忌赛马 [ 46 ]

转自 https://www.cnblogs.com/Open_Source/archive/2010/07/09/1904940.html

解题思路：贪心算法。根本思想是要让田忌花最小的代价来胜一每一场，让齐王花最大的代价来胜每一场。（“代价”可以用比较的两匹马的权值之差来形象地表示）

首先将两人的马排序。

（让田忌每一匹马实现自己的最大价值）这时如果田忌最劣的马是所有中最劣的，就让它跟齐王最强的比较（这时对于田忌的这匹劣马来说并不会比其它的情形坏，因为它注定要输）齐王的最强马没了，对于田忌其他马来说胜率更大，如果田忌最劣的马不是最劣的，说明这匹马强于齐王最劣的，那就让它们比较，让田忌胜出（按照贪心仔细想想，如果让每一匹马的价值最大,其实操作应该更加复杂，假设田忌最差的是t_low，速度为80，齐王最差的是k_low1，速度68，第二差的k_low2 速度79,如果需要价值最大化，应该用t_low去胜K_low2）（但是实际上并不需要，因为t_low2速度大于t_low1,前两场无论田忌怎么出t_low1和2一定胜，但是如果K_low3速度大于t_low3,最终还是2胜一败，虽然实现了最大价值，但是并没有改变结果）

原文：https://blog.csdn.net/lawrencesgj/article/details/8001638 

*
贪心策略：
1，如果田忌的最快马快于齐王的最快马，则两者比。
（因为若是田忌的别的马很可能就赢不了了，所以两者比）
2，如果田忌的最快马慢于齐王的最快马，则用田忌的最慢马和齐王的最快马比。
（由于所有的马都赢不了齐王的最快马，所以用损失最小的，拿最慢的和他比）
3，若相等，则比较田忌的最慢马和齐王的最慢马
3.1，若田忌最慢马快于齐王最慢马，两者比。
（田忌的最慢马既然能赢一个就赢呗，而且齐王的最慢马肯定也得有个和他比，所以选最小的比他快得。）
3.2，其他，则拿田忌的最慢马和齐王的最快马比。
（反正所有的马都比田忌的最慢马快了，所以这匹马必输，选贡献最大的，干掉齐王的最快马）

我的是从最慢的马开始弄的....思路基本相同

#include<iostream>
# include<algorithm>
using namespace std;
int t[1000], k[1000];
int main(void) {
	int n;
	cin >> n;
	while (n) {
		for (int i = 0; i < n; i++)
			cin >> t[i];//田的马
		for (int i = 0; i < n; i++)
			cin >> k[i];//王的马
		sort(t, t + n);
		sort(k, k + n);
		int tlow, klow, tfast, kfast;
		tlow = klow = 0;
		tfast = kfast = n - 1;
		int twin, kwin; twin = kwin = 0;
		for (int i = 0; i < n; i++) {
			if (t[tlow] < k[klow]) {//最差对王最强
				tlow++; kfast--; kwin++;
			}
			else if (t[tlow] == k[klow]) {
				//看快马
				if (t[tfast] > k[kfast]) {
					 tfast--; kfast--; twin++;
				}
				else {//快马相等或者没有王快都是用慢马消耗
					if (k[kfast] > t[tlow])kwin++;
					tlow++; kfast--;
				}
			}
			else {//田忌慢马赢
				tlow++; klow++; twin++;
			}
		}
		cout << (twin - kwin) * 200<<endl;
		cin >> n;//下一轮
	}
	system("pause");
	return 0;
}

下面是我的自检方法：之前一直AC不了，写了个自检来找错误案例

# include<iostream>
#include<algorithm>
#pragma warning (disable:4996)
using namespace std;
int t[1010], k[1010];
int R(void) {//伪随机自检
	int randn= (rand() % 10) + 1;
	for (int i = 0; i < randn; i++) {
		t[i] = (rand() % 99 )+ 1;
		k[i]= (rand() % 99) + 1;
	}
	return randn;
}
//正确答案
int Y(int n) {
	int  i, awin, bwin, afast, bfast, aslow, bslow;
	sort(t, t + n);
	sort(k, k + n);
	awin = bwin = 0;//记录赢的次数 
	afast = bfast = n - 1;//标记最快的马 
	aslow = bslow = 0;//标记最慢的马 
	for (i = 0; i < n; ++i)
	{
		if (t[aslow] >k[bslow])
		{
			awin++;
			aslow++; bslow++;
		}
		else if (t[aslow] < k[bslow])//用最慢马消耗国王的最快马 
		{
			bwin++;
			aslow++; bfast--;
		}
		else//两匹最慢马速度相同时 
		{
			if (t[afast] > k[bfast])
			{
				awin++;
				afast--; bfast--;
			}
			else if (t[aslow] < k[bfast])//如果田忌的最快马不能胜国王的最快马，则用慢马消耗 
			{
				bwin++;
				aslow++; bfast--;
			}
		}
	}
	return (awin - bwin) * 200;
}
//我的答案
int My(int n) {
	int tlow, klow, tfast, kfast;
	tlow = klow = 0;
	tfast = kfast = n - 1;
	int twin, kwin; twin = kwin = 0;
	for (int i = 0; i < n; i++) {
		if (t[tlow] < k[klow]) {//最差对王最强
			tlow++; kfast--; kwin++;
		}
		else if (t[tlow] == k[klow]) {
			//看快马
			if (t[tfast] > k[kfast]) {
				 tfast--; kfast--; twin++;
			}
			else {//快马相等或者没有王快都是用慢马消耗
				if (k[kfast] > t[tlow])kwin++;
				tlow++; kfast--;
			}
		}
		else {//田忌慢马赢
			tlow++; klow++; twin++;
		}
	}
	return (twin - kwin) * 200;
}
int main()
{
	int nn,time=0;
	while ((time++)<100000) {
		cout << time << endl;
		nn = R();
		int yre = Y(nn);
		int mre = My(nn);
		if (yre != mre) {
			for (int i = 0; i < nn; i++) {
				cout << t[i] << " ";
				if (!((i + 1) % 10))cout << endl;
			}
			cout << "出现答案不同的案例：" << endl;
			cout << "--------------------------------";
			cout << endl << nn << endl;
			cout << "________正确答案：" << yre << endl;
			cout << "________我的答案：" << mre << endl;
			cout << "---------------------------------";
			cout << endl << endl << endl;
			for (int i = 0; i < nn; i++) {
				cout << k[i] << " ";
				if (!((i + 1) % 10))cout << endl;
			}
			system("pause");
		}
	}
	system("pause");
	return 0;
}