当前位置: 代码迷 >> 综合 >> HDOJ-1052 Tian Ji -- The Horse Racing(贪心算法)
  详细解决方案

HDOJ-1052 Tian Ji -- The Horse Racing(贪心算法)

热度:58   发布时间:2023-12-09 20:52:41.0

题目: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