题解：P10417 [蓝桥杯 2023 国 A] 第 K 小的和

abc1856896 · 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;
}