The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-M. Many CF Rounds vs Capoo 猫猫虫打 CF（这种有一个元素有两个值的这种东西，可以把他们看作是一条线段，画在这个数轴上面，兴许可以看出些什么，至少比干瞪眼好） · znzryb
## 题目大意
**题目描述**
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$。
1. 参加第 $7$ 场比赛（$a_7=0, b_7=7$）：满足 $x \le a_7$（$0 \le 0$），参加后 $x$ 更新为 $\max(0, 7) = 7$。
1. 参加第 $5$ 场比赛（$a_5=18, b_5=3$）：满足 $x \le a_5$（$7 \le 18$），参加后 $x$ 更新为 $\max(7, 3) = 7$。
1. 参加第 $6$ 场比赛（$a_6=16, b_6=9$）：满足 $x \le a_6$（$7 \le 16$），参加后 $x$ 更新为 $\max(7, 9) = 9$。
1. 参加第 $10$ 场比赛（$a_{10}=15, b_{10}=17$）：满足 $x \le a_{10}$（$9 \le 15$），参加后 $x$ 更新为 $\max(9, 17) = 17$。
1. 参加第 $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 从小到大排比较好，
```cpp
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代码
::: 源代码
```cpp
/**
* 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……）