题解：P14593 [LNCPC 2025] 猫猫虫打 CF

· · 题解

思路

考虑贪心。

不难想到贪心策略，按照 \max(a_i,b_i) 升序排序。

若存在一组 \max(a_i,b_i)>\max(a_j,b_j) 且 i<j。若 b_i>a_j 则交换两组只可能多打而不可能少打。若 a_i>b_j，交换后不变。故交换后一定不会少参加。

所以只要贪心后正常模拟即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,nw,cnt;
struct node{
    int x,y;
}s[1000001];
bool cmp(node a,node b){//贪心策略
    if(max(a.x,a.y)!=max(b.x,b.y)) return max(a.x,a.y)<max(b.x,b.y);
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].x>>s[i].y;
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++){//正常模拟
        if(nw<=s[i].x) {
            nw=max(nw,s[i].y);
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}