算法思路解析
1. 排序处理:首先将双方的马匹按速度升序排序,这样可以方便地比较最快和最慢的马。
2. 贪心策略:
* 当田忌最快的马比国王最快的马快时,直接比赛,田忌赢200两
* 当田忌最快的马比国王最快的马慢时,用田忌最慢的马消耗国王最快的马,最小化损失
* 当双方最快的马速度相同时,比较最慢的马:
* 如果田忌最慢的马更快,就用最慢的马比赛赢200两
* 否则用田忌最慢的马消耗国王最快的马
3. 双指针技巧:使用左右指针分别跟踪当前最快和最慢的马,逐步缩小比较范围。
这个算法的时间复杂度主要是排序的O(nlogn)和单次遍历的O(n),总体为O(nlogn),能够高效解决问题。