题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和$n$行，每行$2$个数$a[i]$和$b[i]$，范围都在$[0,n]$内。

你有$n$个朋友，第$i$个朋友有$i$元钱。你想邀请朋友参加聚会。

对于第$i$个朋友，只有聚会中最多有$a[i]$个人比他的钱多，最多有$b[i]$个人比他的钱少，他才会参加聚会。

输出你最多可以邀请多少个人。

输入样例

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

输出样例

2
1
2

算法

二分答案

对于任何一个朋友$i$，前$i-1$个朋友的钱肯定比他少。我们可以二分这个最多的邀请数，对于一个给定的目标邀请数$x$，从左往右遍历所有朋友。前面被邀请的朋友（钱比$i$少的）数量为$cnt$，如果$b[i] \geq cnt$且$a[i] \geq x-cnt-1$，说明当前钱比他少的人数和钱比他多的人数都符合要求，他可以被邀请，遍历完所有朋友之后：

1. 如果$cnt \geq x$，说明邀请$x$个朋友是可行的，记录一下答案然后往右搜索看能不能更大。
2. 如果$cnt \lt x$，说明$x$给大了，往左搜索。

复杂度分析

时间复杂度

最多邀请$n$人，最少邀请$1$人，所以是在区间$[1,n]$上进行二分。而对于一个给定的$x$，需要遍历检查$i \in [1,n]$
是否满足条件，时间复杂度是$O(n)$的。因此，算法整体的时间复杂度是$O(nlog_2n)$。

空间复杂度

除了题目给出的$a$、$b$两个数组，只使用了有限几个变量。因此，算法的额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int t, n, a[N], b[N];

bool check(int x) {
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(b[i] < cnt || a[i] < x - cnt - 1) continue;
        cnt++;
    }
    return cnt >= x;
}

void solve() {
    int l = 1, r = n;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid)) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    printf("%d\n", r);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);
        }
        solve();
    }
    return 0;
}