B3928 [GESP202312 四级] 田忌赛马 题解

tder · 2024-01-29 10:38:08 · 题解

于 2024-08-20 修正一处笔误。

宝 ~ 宝 ~ 巴 ~ 士 ~ 快 ~ 乐 ~ 启 ~ 蒙 ~（啊什么？这才是真正的宝宝巴士？）。

好吧不要太离谱。

参考上面的故事，考虑将所有马的速度排序，下面就是一个例子：

那么，显然，我们为了赢得更多场，即需要找出尽量多组 u_i>v_j 的关系，考虑寻找在上面的连不等式中尽可能相近的数量关系。

在上面的例子中，从右往左看：

• 同理，v_2 是小于 u_3 的最大的 v_i，有一组 u_3>v_2。

因此，共 2 组。

总结一下，从 u_i 的最小值开始，若存在 v_i 小于当前的 u_i，取最接近的；若不存在，则选择与当前最大的 u_i 比赛。

模拟并统计胜利场数即可。