cc准备举办一场派对，他希望邀请他的朋友们过来参加，并且每个人都能玩得开心

cc有 $n$ 位朋友，第 $i$ 位的身价为 $i$

如果第 $i$ 位朋友参加派对，并且玩得开心，当且仅当派对上至多有 $X_i$ 个人比他身价严格大于他，至多有 $Y_i$ 个人身价严格小于他

cc想知道，他最多能邀请来多少人，并且他们每个人都玩得开心

输入描述

第 $1$ 行给出一个数 $T$ ，表示有 $T$，($1\le T\le 10^4$) 组数据

对于每一组数据

第 $1$ 行给出一个数 $n$，($1\le \sum n\le 2\times 10^5$)，表示有 $n$ 个朋友

接下来 $n$ 行，每一行给出两个数 $X_i$，$Y_i$，($0\le X_i,Y_i<n$)

输出描述

输出一个数，表示cc所能邀请的最多的人的人数

样例输入

3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1

样例输出

2
1
2

解题思路

根据题意，我们有这样一种直觉：

所想邀请的人数越多，越不容易成功；

所想邀请的人数越少，越容易成功。

所以我们采用二分搜索：

int bin_search() {int l = 0, r = n + 1, mid;while (l + 1 != r) {mid = l + r >> 1;if (judge(mid)) l = mid;else r = mid;}return l;
}

但是如何judge(mid)是否符合题意呢？

考虑一种通常的情况：

我们遍历每一个人，现在遍历到第i个。

对于他，我们已知其前面已选择了cnt个人。

1）如果这个人不能来参加聚会，那么就简单跳过即可；

2）如果这个人能够参加聚会，且mid是符合题意的，那么在其之后至少还会再选择mid-cnt-1个人。

bool judge(int x) {int cnt = 0;for (int i = 1; i <= n; i++) {if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;}return x <= cnt;
}

然后我们来解决两个可能存在的疑问：

1）按照如上的统计方式，我们最后得到的cnt可能大于x，这会导致之前判断条件mid-cnt-1失去意义。

这个问题对结果没有影响，把多余的人删去就可以了。

2）按照如上的贪心算法，我们的统计结果不一定是最大的cnt，因为可能前面选择的人数过多，导致更多的人不再符合条件cnt <= ys[i]。

进行贪心证明：

假设存在组合，使得在不选前面cnt个人的情况下，所选的人数能够变为cnt+k。

那么根据已知条件，我们选择cnt+k个人中靠前的cnt个人，显然把他们替换为之前的cnt个人后仍然能够符合题意。

所以假设不成立。

最后，AC代码如下：

#include <iostream>
using namespace std;
const int max_n = 2e5;int xs[max_n + 1], ys[max_n + 1];
int n;bool judge(int x) {int cnt = 0;for (int i = 1; i <= n; i++) {if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;}return x <= cnt;
}int bin_search() {int l = 0, r = n + 1, mid;while (l + 1 != r) {mid = l + r >> 1;if (judge(mid)) l = mid;else r = mid;}return l;
}int main() {int t;cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++) cin >> xs[i] >> ys[i];cout << bin_search() << endl;}return 0;
}