题目描述

难度分:$1400$

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

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和两个长为$n$的数组$a$，$b$，元素范围在$[1,10^9]$。

• 把下标$1$，$2$，…，$n$分成两组，记作$P$和$Q$。
• 对于$P$中的下标$i$，计算$a[i]$的最大值$m$。
• 对于$Q$中的下标$j$，计算$b[j]$的和$s$。

输出$max(m, s)$的最小值。

例如$a=[3,7,4,5]$，$b=[2,1,2,4]$，如果$P=[1,4]$，$Q=[2,3]$，那么$m=5$，$s=3$，所以$max(m,s)=5$。

输入样例

4
4
3 7 4 5
2 1 2 4
4
1 2 3 4
3 3 3 3
2
1 2
10 10
2
10 10
1 2

输出样例

5
3
2
3

算法

二分答案

这个题一看要求的东西是最大值的最小值，想到的就是二分答案，然后写了一版二分，测了样例没问题就提交AC了。过了之后可以分析一下单调性，对于一个给定的$limit$，我们希望所有被选出来的$a[i]$的最大值都不超过$limit$，可以直接遍历$i \in [1,n]$，如果$a[i] \gt limit$就把$b[i]$累加到$s$上，只要遍历完成后$s \leq limit$，这个$limit$就是可以达成的。此时我们发现，如果增大$limit$，肯定也是可以达成的，因为这时候满足$a[i] \leq limit$的$a[i]$会更多，说明累加到$s$上的$b[i]$会更少，所以具有单调性，可以二分答案来做。

复杂度分析

时间复杂度

二分时的$check$函数时间复杂度为$O(n)$，只遍历了一遍$i \in [1,n]$。外面的二分时间复杂度为$O(log_2A)$，其中$A$是元素的上界，本题中$A \leq 10^9$。算法整体的时间复杂度为$O(nlog_2A)$。

空间复杂度

除了输入的数组$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 limit) {
    long long s = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > limit) {
            s += b[i];
            if(s > limit) return false;
        }
    }
    return s <= limit;
}

int solve() {
    int l = 1, r = 1e9;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) {
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    return r;
}

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