官方题解

T2 午枫的卡片游戏

题目大意

双方都有 $n$ 卡片，小枫告诉了小午自己的出牌顺序，双方进行比较点数，如果小午点数大本轮小午获胜，否则小枫获胜。求最终谁的胜场多。

解题思路

我们可以通过“田忌赛马”的思想，用自己尽量小点数的卡片和对方尽量大点数的卡片进行比较，最大化的减少敌方战力的同时最小化减少己方战力。让我们赢的时候尽量也选取最接近对方点数的卡片。

因此原本的卡片顺序已经不重要了，我们可以将双方的卡片排序，通过双指针模拟比较双方的点数。

时间复杂度 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n;cin>>n;
    vector<int>a(n+1),b(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a.begin()+1,a.end(),greater<int>());
    sort(b.begin()+1,b.end());

    int resa=0,resb=0;
    int l=1,r=n;
    for(int i=1;i<=n;i++){
        if(a[i]>=b[r]){
            l++;
            resb++;
        }
        else{
            r--;
            resa++;
        }
    }
    if(resa>resb) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}