The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-M. Many CF Rounds vs Capoo 猫猫虫打 CF（这种有一个元素有两个值的这种东西，可以把他们看作是一条线段，画在这个数轴上面，兴许可以看出些什么，至少比干瞪眼好）

题目大意

题目描述
Capoo 的初始 rating 为 $x=0$。
现在有 $n$ 场比赛，对于第 $i$ 场比赛，它的难度为 $a_i$，隐藏分数为 $b_i$。每场比赛最多只能参加一次。
只有当当前 rating $x \le a_i$ 时，Capoo 才能参加第 $i$ 场比赛。参加完该场比赛后，Capoo 的 rating 将会更新为 $\max(b_i, x)$。
你可以自由安排参加这 $n$ 场比赛的顺序，求 Capoo 最多能参加多少场比赛。

输入格式
第一行包含一个整数 $n$（$1 \le n \le 10^6$）。
接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$0 \le a_i, b_i \le 10^{18}$），分别表示第 $i$ 场比赛的难度和隐藏分数。

输出格式
输出一行一个整数，表示 Capoo 最多能参加的比赛场数。

样例

输入:
10
19 18
6 15
5 8
4 20
18 3
16 9
0 7
5 17
2 13
15 17

输出:
5

样例解释

注意，这个人比较喜欢挑战这个难题。
一种最多参加 $5$ 场比赛的合法顺序如下：

1. 初始时 $x = 0$。

2. 参加第 $7$ 场比赛（$a_7=0, b_7=7$）：满足 $x \le a_7$（$0 \le 0$），参加后 $x$ 更新为 $\max(0, 7) = 7$。

3. 参加第 $5$ 场比赛（$a_5=18, b_5=3$）：满足 $x \le a_5$（$7 \le 18$），参加后 $x$ 更新为 $\max(7, 3) = 7$。

4. 参加第 $6$ 场比赛（$a_6=16, b_6=9$）：满足 $x \le a_6$（$7 \le 16$），参加后 $x$ 更新为 $\max(7, 9) = 9$。

5. 参加第 $10$ 场比赛（$a_{10}=15, b_{10}=17$）：满足 $x \le a_{10}$（$9 \le 15$），参加后 $x$ 更新为 $\max(9, 17) = 17$。

6. 参加第 $1$ 场比赛（$a_1=19, b_1=18$）：满足 $x \le a_1$（$17 \le 19$），参加后 $x$ 更新为 $\max(17, 18) = 18$。
   总计参加了 $5$ 场比赛，可以证明这是最多能参加的比赛场数。

思路讲解

将所有比赛分成两组：

• 安全组 A：$b_i \le a_i$。参加后 $x \leftarrow \max(x, b_i) \le a_i$，也就是说参加这场比赛不会把 $x$ 抬到超过它自身的门槛 $a_i$。对后续的影响很温和。

• 危险组 B：$b_i > a_i$。参加后 $x$ 必然跳到 $b_i$（因为 $b_i > a_i \ge x$），对后续影响大。

为什么这个分组有用？因为安全组内部，如果按 $a_i$ 升序排列，全部都能参加——每次参加后 $x \le a_i$，而下一场的 $a$ 更大，必然满足条件。所以安全组是"稳赚不赔"的。

下一步应该关注：安全组全做了，危险组怎么尽可能多地塞进来**？（把安全组给固定住）**

第三层：排序与交错——两组的最优合并策略

• 安全组按 $a_i$ 升序排。

• 危险组按 $b_i$ 升序排（参加后 $x$ 跳到 $b_i$，越小越好，留给后面的空间越大）。

一下的这个规则就是，在上面情况下，B 不会影响 A？（先不要去想 B 会不会生效）

关键的交错规则：在做每一个危险组比赛 $B_j$（$b$ 值为 $b_j$）之前，先把安全组中所有 $a_i < b_j$ 的比赛做完。

为什么？做完 $B_j$ 后 $x = b_j$，那些 $a < b_j$ 的安全组比赛就再也做不了了。提前做掉它们不会抬高 $x$（因为安全组的 $b \le a < b_j$），不影响 $B_j$ 的可行性。

这样，安全组的比赛一场都不会浪费——它们总是在 $x$ 被抬高之前被消化掉。最终的答案就是：

$$\text{安全组全部} + \text{按上述交错策略能做的危险组数量}$$

不难想到，危险组按照这个 b 从小到大排比较好，

auto forward=[&]() -> bool {
    while (idx1<SZ(safeA) && idx2<SZ(dangerA) && safeA[idx1].a<dangerA[idx2].b) {
        cur_ability=max(cur_ability,safeA[idx1].b);
        ++idx1;
    }

    if (cur_ability<=dangerA[idx2].a) {
        cur_ability=max(cur_ability,dangerA[idx2].b);
        ++ans;
    }
    ++idx2;
    if (idx2<SZ(dangerA)) {
        return true;
    }
    return false;
};
while (forward()) {
}

AC代码

源代码

/**
 * Problem: M. Many CF Rounds vs Capoo
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/M
 * Created: 2026-03-12 13:41:24
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct A_b {
    ll a,b;
};
struct Cmp {
    bool operator()(const A_b &a,const A_b &b) const {
        if (a.a!=b.a) return a.a<b.a;
        return a.b>b.b;
    }
};
struct Cmp2 {
    bool operator()(const A_b &a,const A_b &b) const {
        if (a.b!=b.b) return a.b<b.b;
        return a.a<b.a;
    }
};
void Solve() {
    ll N;
    cin >> N;
    // vector<A_b> A(N+2);
    vector<A_b> safeA,dangerA;
    for (int i=1;i<=N;++i) {
        ll a,b;
        cin>>a>>b;
        if (a>=b) {
            safeA.push_back({a,b});
        }else {
            dangerA.push_back({a,b});
        }
    }
    ll ans=SZ(safeA);
    sort(all(safeA),Cmp());
    sort(all(dangerA),Cmp2());
    ll idx1=0,idx2=0;
    ll cur_ability=0;
#ifdef LOCAL
    for (int i=0;i<SZ(safeA);++i) {
        debug(i);
        debug(safeA[i].a);
        debug(safeA[i].b);
    }
    cend;
    for (int i=0;i<SZ(dangerA);++i) {
        debug(i);
        debug(dangerA[i].a);
        debug(dangerA[i].b);
    }
    cend;
#endif

    auto forward=[&]() -> bool {
        while (idx1<SZ(safeA) && idx2<SZ(dangerA) && safeA[idx1].a<dangerA[idx2].b) {
            cur_ability=max(cur_ability,safeA[idx1].b);
            ++idx1;
        }

        if (cur_ability<=dangerA[idx2].a) {
            cur_ability=max(cur_ability,dangerA[idx2].b);
            ++ans;
        }
#ifdef LOCAL
        debug(idx1);
        debug(idx2);
        debug(ans);
        debug(cur_ability);
        debug(dangerA[idx2].a);
        debug(dangerA[idx2].b);
#endif
        ++idx2;
        if (idx2<SZ(dangerA)) {
            return true;
        }
        return false;
    };
    while (forward()) {
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）