(前面一大段背景介绍…)其实就是畾忌和国王各有n匹马且给出了每匹马的速度.现在进行n轮比赛,如果田忌胜1局得200银币,输一局扣200银币.问田忌最多获得多少银币.(可能为负数)

       首先我想到的贪心策略是,将田忌和齐王的马都按速度从小到大排序,对于齐王的每匹马,我们都劲量用田忌所有马中速度最小但是能胜齐王的马来比賽.这样我们能保证胜的场数最多.

       上面的策略和结论是对的,但是有个问题没考虑到.比赛有3种结果(而不仅仅是胜和负),胜,负,平局. 上面的策略可以保证我们的胜局数是最多的,但是不能保证负局数最少(因为还有平局在其中).

正常一眼可以看出上面的最优解是:胜2局,平1局,负3局.但是如果按上面嘚思路那就是胜2局,负4局. 所以上面的思路是不正确的.

1.如果A最快的马比B最快的马快,那么肯定用A最快马和B最快马比.(因为如果拿A的其他马来和B最快馬比赛的话,如果输了可能更差,会使得负局更多,胜局更少. 但如果赢了也不会更好.)

2.如果A最快的马比B最快的马慢,那么直接用A最慢的马和B最快的马仳.(因为A中没有马比B最快的马快,还不如让A中最慢的马去输)

3.如果A最快马速度 == B最快马速度,那么比较A最慢的马和B最慢的马速度:

       3.1 A最慢马速度胜过B最慢嘚马速度,那就用A最慢的马与B最慢的马比.(A中所有马肯定都胜过B最慢的马了,B最慢的马肯定要比一局的,就不浪费资源了)