自动搬运

查看原文

来自洛谷，原作者为

	abc1856896 谦虚谨慎，砥砺前行。

搬运于2025-08-24 22:57:47，当前版本为作者最后更新于2024-05-10 13:58:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定两个序列 $A,B$，长度分别为 $n,m$。

设另有一个序列 $C$ 中包含了 $A,B$ 中的数两两相加的结果。

问 $C$ 中第 $K$ 小的数是多少。

solution

因为 $k \le 10^{10}$，所以我们不能枚举。

考虑二分。

左右边界都是简单的，一个设为 $0$，一个设为极大值即可。

判断函数也显而易见的：枚举 $A$ 序列里面的数，然后再找 $B$ 序列能和 $A$ 序列里选出来的数加起来之和小于等于 $t$ 即可。

但这样判断函数的时间复杂度是 $O(nm)$，会超时。

考虑优化。

超时的问题出现在判断函数的时间复杂度是 $O(nm)$。所以我们将枚举 $B$ 序列的循环改成二分即可。注意提前排序。

这样，判断函数的时间复杂度是 $O(n \log m)$。不会超时。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, a [100005], b [100005];
bool check ( int x ) { 
    int sum = 0;
    for(int i = 0 ; i < n ; i++ ) {
        sum += upper_bound ( b, b + m, x - a[i] ) - b;
    }
    return sum >= k;
}
signed main(){
    cin >> n >> m >> k;
    for(int i = 0 ; i < n ; i++ ) {
        cin >> a [i];
    }
  
    for(int i = 0 ; i < m ; i++ ) {
        cin >> b[i];
    }
    sort( b, b + m );
    int l = 0, r = INT_MAX;
    while(l + 1 < r ) {
        int mid = ( l + r ) / 2;
        if (check ( mid ) ) r = mid;
        else l = mid;
    }
    cout << r;
    return 0;
}