本文主要是介绍算法篇：贪心算法解决田忌赛马问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*田忌赛马：贪心算法
问题分析
这是一道很经典的贪心算法入门题。 这道题贪心的思想是 要把每一匹马的作用发挥到最大，把已
方赢的概率增加到最大.
我是从双方慢马的角度来分析的，其实快马和慢马的思路差不多。
用田忌最慢的马与王最慢的马相比较:
1.如果田忌的慢马比王的慢马要快
果断把先用田忌的慢马先赢一把（这样赢是代价最小的）
2.如果田忌的慢马比王的慢马要慢
果断把这匹慢马与王最快的马比赛（因为反正都要输，这样我输的价值更大，因为我把最快的马比下去了，可
以增加后面其他马赢的机会）
3.如果田忌的慢马与王的慢马速度一样
->拿田忌最快的马和王最快的马比较
1)如果田忌快马比王快马快，那就拿这匹快马赢一局，之所以需要判断是因为我想让我最慢的马收益更大，如
果我的快马比王的快马快就没必要让慢马和这匹快马比了，我可以直接赢一盘。然后让我最慢的马去和王的一
匹比我剩下所有的马都要快的马比赛，这样我的慢马收益才是最大的。
2)如果田忌快马比王快马慢，那就拿田忌最慢的马与王最快的马比赛，这样的话我可以增加已方后面的马赢的
概率，因为你把最快的马拉走了.
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1005],b[1005];
int cmp(int x,int y)
{
return x<y;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n){
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
sort(a,a+n,cmp);
sort(b,b+n,cmp);
//分别定义田忌和国王的快慢马
int cnt=0,t1=0,k1=0,t2=n-1,k2=n-1;
for(int i=0;i<n;i++){
if(a[t2]>b[k2]){//田快>王快
cnt+=200;
t2--;
k2--;
}
else if(a[t2]<b[k2]){// 田快<王快
cnt-=200;
t1++;
k2--;
}
else{//快马相等 ,比较慢马。
if(a[t1]>b[k1]) {
cnt+=200;
t1++;
k1++;
}
else {
if(a[t1]<b[k2]){
cnt-=200;
t1++;
k2--;
}
}
}
}
cout<<cnt<<endl;
}
return 0;
}
参考链接：https://blog.csdn.net/weixin_46447561/article/details/105083909
https://www.jianshu.com/p/5d85cb3b7ed2
这篇关于算法篇：贪心算法解决田忌赛马问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
