题解

1 条题解

  • 0
    @ 2023-05-12 11:33:37

    假设田忌最快的马为 \(f_1\),最慢的马为 \(s_1\),国王最快的马为 \(f_2\),最慢的马为 \(s_2\)。要让田忌赢尽可能多的比赛,分以下情况讨论:

    1、若 \(s_1>s_2\),让 \(s_1\ PK\ s_2\),此时田忌会赢一场。

    2、若 \(s_1<s_2\),让 \(s_1\ PK\ f_2\),因为田忌的马 \(s_1\) 无论如何都是输,就让这匹马当炮灰去把国王最快的马 PK 下来,让剩下的马有更多赢的机会。

    3、若 \(s_1=s_2\) ,田忌的这匹马要么去平一局,要么去当炮灰,一时难以决定!那么我们不妨先比较最快的马看看:

      3.1 若 \(f_1>f_2\),让 \(f_1\ PK\ f_2\),因为田忌最快的马 \(f_1\) 肯定会赢,就让它去 PK 掉国王最快的马 \(f_2\),剩下的马就会有更多赢的机会。

      3.2 若 \(f_1<=f_2\),让 \(s_1\ PK\ f_2\),因为国王最快的马 \(f_2\) 肯定不会输,就让最慢的马 \(s_1\) 去PK掉 \(f_2\)。剩下的马就会有更多赢的机会。

  • 1

信息

ID
1300
难度
3
分类
贪心 | 动态规划 点击显示
标签
递交数
2
已通过
1
通过率
50%
被复制
3
上传者