思路

Exchange Argument 模板题。

考虑两个二元组

(a_1,b_1),(a_2,b_2)

在什么情况下先选择 1，再选择 2：

若 $a_1 < b_2$ ，如果先选择 2，1 一定选择不了，一定不优于原先策略。
若 $b_1 < a_2$ ，此时能不能取到 2 只取决于当前 $x$ 的取值，也就是说无论是 12，还是 21，所带来的影响是一样的。

当

a_2 < b_1

或

b_2 < a_1

时显然同上，先选 2 再选 1 是不劣的。整合一下上面的分析，按照

\max(a_i,b_i)

排序，当

\max(a_i,b_i)

相等时，再按照

a_i,b_i

分别排序。最后按照排序后的顺序模拟即可。

Code

CPP

#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long
#define chmax(a,b) (a = max(a,b))

using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 10;
int n,d,ans;
pii arr[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

signed main(){
    n = read();
    for (re int i = 1;i <= n;i++) arr[i].fst = read(),arr[i].snd = read();
    sort(arr + 1,arr + n + 1,[](const pii &a,const pii &b){
        if (max(a.fst,a.snd) != max(b.fst,b.snd)) return max(a.fst,a.snd) < max(b.fst,b.snd);
        else if (a.fst != b.fst) return a.fst < b.fst;
        else return a.snd < b.snd;
    });
    for (re int i = 1;i <= n;i++){
        if (d <= arr[i].fst) ans++,chmax(d,arr[i].snd);
    } printf("%lld",ans);
    return 0;
}

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

文章操作

思路

Code

相关推荐

评论

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