当前位置:首页 > 比赛题解 > 2023年GESP四级田忌赛马(洛谷B3928题):从田忌赛马学贪心算法

2023年GESP四级田忌赛马(洛谷B3928题):从田忌赛马学贪心算法

12小时前比赛题解26

截图未命名.jpg 2023年GESP四级田忌赛马(洛谷B3928题):从田忌赛马学贪心算法 贪心算法 双指针技巧 田忌赛马 GESP GESP四级 洛谷题解 C++ 第1张

一、问题背景与算法思路

田忌赛马问题是一个经典的贪心算法案例,要求在双方马匹速度已知的情况下,通过合理安排对战顺序获取最大胜利场次。解题关键在于排序后采用双指针策略,以最优方式匹配双方马匹。

二、完整代码解析(含详细注释)

#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;
}

三、关键算法解析

  1. 排序预处理:将双方马匹按速度升序排列,为后续策略奠定基础

  2. 双指针策略:使用i、j两个指针分别追踪双方当前最弱的马

  3. 贪心选择

    • 能赢则直接对战(双方最弱马比较)

    • 必输则战略性放弃(用最弱马消耗对方最强马)

四、常见问题解答

Q:为什么要先排序? A:排序后可以方便地获取双方当前最弱/最强的马,这是贪心策略的基础。

Q:为什么必输时要消耗对方最强马? A:这样可以保留我方较强的马去赢得更多比赛,是全局最优的选择。

Q:如何证明这个策略的正确性? A:可以通过数学归纳法证明,任何其他安排方式都无法获得更多胜利场次。


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。