题目描述
“田忌赛马”是中国历史上一个著名的故事.
故事新编
大约2300年前, 齐国大将田忌喜欢和国王赛马, 并且约定: 每赢一场, 对方就要付200元.
假设已知田忌和国王的各自马匹的速度都不相同, 请计算田忌最好的结果是什么’.输入
输入包含多组测试样例.
每组样例的第一行是一个非负整数n, 表示田忌和国王各自参赛的马匹数量.
接下来一行的n个整数表示田忌的马的速度, 再接下来一行的n个整数表示国王的马的速度.
n为0时, 表示输入数据的结束.输出
每组数据输出一行, 表示田忌最多能够赢得的金额.
数据范围
n<=1000
输入样例
3
92 83 71
95 87 74
2
20 19
22 18
0输出样例
200
0
思路分析
? "田忌赛马"的故事在中国可谓是家喻户晓, 这个故事不仅体现出战国时期大军事家孙膑的聪明才智, 对我们在做决策时也有不小的启示. 下面我们一起来来看一下这个新编的故事.
? 从故事本身中我们不难发现，田忌只有在有把握赢的情况下拿出快马与齐王比，否则就拿最慢的马来和齐王最快的马“同归于尽”, 最大程度的削弱对手的整体战斗力, 从而达到整体最优解.
? 下面我们就结合代码来详细分析一下这道题的解法 (因为这样比较方便)
样例代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin>>n; //田忌和国王各自参赛的马匹数量
while(n!=0)
{
int *tian=new int [n]; //使用动态数组来储存田忌各个马匹的速度
for(int i=0;i<n;i++)
cin>>tian[i];
int *king=new int[n]; //与上文同理
for(int i=0;i<n;i++)
cin>>king[i];
sort(tian,tian+n); sort(king,king+n); //对两方马匹的速度进行排序
int count=0; //用于记录田忌胜利的局数
int j=n-1;
for(int i=n-1;i>=0&&j>=0;)
{
if(tian[i]<king[j]) //如果田忌第i匹马的慢于国王第j匹马的, 则进行下一轮比较, 直到田忌第i匹马的速度快于国王的第x匹马
// 注意: 此时要不改变田忌将要出战的马
j--;
else //如果田忌的马的快于国王的马, 则派这匹马出战, count++
{
count++;
j--;
i--;
}
}
cout<<(count-(n-count))*200<<endl; //胜利的场数减去失败的场数, 再乘200, 即最后赢的钱数
cin>>n;
}
}
补充
? 因为这个题目如果不结合具体代码来解释, 会颇为麻烦一些, 感觉之后许多题目也要如此解释 (写到这里我想起了三体人, 如果我们能像三体人那样通过思维直接交流, 并且可以将知识以"思维"的方式储存, 人与人之间的交流就可以变得简单不少吧) 希望可以看明白啊,如果看不太懂, 也可以在下方留言或者参考其他题解.
? 不过, 在这个专栏一开始, 我就曾说过类似于"这专栏是为我而写"的话, 既然如此, 我为什么还要解释地这么清楚呢? 因为我害怕自己之后会忘记, 所以就事先解释清楚, 避免出现"当你写下这句话的时候你才真正理解这句话"的现象.
? 我把代码发给我同学之后, 才知道我这种算法叫做—贪心算法
? **定义: ** 贪心算法 (又称贪婪算法) 是指, 在对问题求解时, 总是做出在当前看来是最好的选择. 也就是说, 不从整体最优上加以考虑，通过这种算法所做出的是在某种意义上的局部最优解. —摘自百度