题目:HDOJ-1052
题目描述:就是田忌赛马,但是要注意两边存在马速度相同的情况。
分析: (看了各路大佬的题解Orz,自我总结一下)
先排序,这里从快到慢排序;
1.田忌最快马>王最快马(贪心,毫无疑问,进行比赛后获胜)
2.田忌最快马<王最快马(同样的,既然赢不了,用最慢马去消耗掉最快马)
3.田忌最快马=王最快马(要比较两者最慢马,因为没考虑这个WA了很多次…)
a.田忌最慢马>王最慢马
田忌:90 60
王:90 50
①60-90 90-50 赢一场,输一场
②90-90 60-50 平一场,赢一场
显然方案②更优,以贪心而言,能赢一场是一场,先让最慢马进行比赛,相等的最快马留给下一次判断。(再判断下一对最慢马)
b.田忌最慢马<王最慢马
田忌:90 40
王:90 70
①90-90 40-50 平一场,输一场
②40-90 90-70 赢一场,输一场
显然方案②更优,既然最慢马也比不过,那就只能用来消耗其相等的最快马,让田忌的最快马保留。
c. 田忌最慢马=王最慢马(最坑的来了,又因为没分析清楚这个继续WA了很多次…)
一开始直接用两个数据分析
田忌:90 70
王:90 70
①90-90 70-70 ②90-70 70-90 效果一样唉(遂WA)
试了试三个
田忌:90 80 60
王:90 70 60
①90-90 60-60 80-70 赢一场,平两场
②60-90 90-70 80-60 赢两场,平一场
根据贪心,觉得与其让最慢马去消耗,输一场,不如让相同的最慢马平一场,但是这里又不能这样贪心,因为可能消耗掉王的当前最快马的效益更高,而且田忌的最快马还在,(不相等时)至少可以赢王的最慢马,分数依旧打平。
*这里还有一个点:*就是用田忌的最慢马去消耗王的最快马时田忌不一定会输!
例如:田忌:90 90 90
王:90 90 90
此时加一个特判,当相等时直接break;结束
以下AC代码
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a, int b)
{
retur