2023年GESP四级田忌赛马(洛谷B3928题):从田忌赛马学贪心算法
一、问题背景与算法思路
田忌赛马问题是一个经典的贪心算法案例,要求在双方马匹速度已知的情况下,通过合理安排对战顺序获取最大胜利场次。解题关键在于排序后采用双指针策略,以最优方式匹配双方马匹。
二、完整代码解析(含详细注释)
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); // 关闭同步提升IO速度 cin.tie(nullptr); // 解除cin与cout的绑定 int N; cin >> N; // 读取马匹数量 vector<int> u(N), v(N); // u存储我方马速,v存储田忌马速 for (int i = 0; i < N; ++i) cin >> u[i]; for (int i = 0; i < N; ++i) cin >> v[i]; // 对双方马匹按速度升序排序 sort(u.begin(), u.end()); sort(v.begin(), v.end()); int wins = 0; // 胜利场次计数器 int i = 0, j = 0; // 双指针:i-我方指针,j-田忌指针 // 核心双指针算法 while (i < N && j < N) { if (u[i] > v[j]) { // 我方最弱马能赢对方最弱马时,直接对战 ++wins; ++i; ++j; } else { // 我方最弱马必输时,让它对战对方最强马 ++i; } } cout << wins << endl; return 0; }
三、关键算法解析
排序预处理:将双方马匹按速度升序排列,为后续策略奠定基础
双指针策略:使用i、j两个指针分别追踪双方当前最弱的马
贪心选择:
能赢则直接对战(双方最弱马比较)
必输则战略性放弃(用最弱马消耗对方最强马)
四、常见问题解答
Q:为什么要先排序? A:排序后可以方便地获取双方当前最弱/最强的马,这是贪心策略的基础。
Q:为什么必输时要消耗对方最强马? A:这样可以保留我方较强的马去赢得更多比赛,是全局最优的选择。
Q:如何证明这个策略的正确性? A:可以通过数学归纳法证明,任何其他安排方式都无法获得更多胜利场次。
原创内容 转载请注明出处