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

知识点：排序、贪心、双指针。

解题思路

把双方马速升序排列，依次用己方马尝试战胜对方当前最慢的未配对马，能赢就完成一场配对。

为什么正确

能战胜当前最慢对手的最小可用马用于此场，不会削弱其他可获胜配对；交换论证可保持最优胜场数。

易错点

题目目标是最大胜场数；速度相等不算胜，判断必须严格大于。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n),b(n);
    for(int &x:a)cin>>x;
    for(int &x:b)cin>>x;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int j=0;
    for(int x:a)if(j<n&&x>b[j])j++;
    cout<<j;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。