Problem Description
给定\(n\)个正整数\(a_1,a_2,\dots,a_n\)和\(m\)个正整数\(b_1,b_2,\dots,b_m\)。
请在\(n\times m\)个\(a_i + b_j(1\leq i\leq n,1\leq j\leq m)\)中，找到第\(k\)小的数（不去重）。
Input
第一行包含一个正整数\(T(1\leq T\leq 10)\)，表示测试数据的组数。
每组数据第一行包含三个正整数\(n,m,k(1\leq n,m\leq 100000,1\leq k\leq n\times m)\)。
第二行包含\(n\)个正整数\(a_1,a_2,\dots,a_n(1\leq a_i\leq 10^8)\)。
第三行包含\(m\)个正整数\(b_1,b_2,\dots,b_n(1\leq b_i\leq 10^8)\)。
输入样例
1
3 4 7
5 4 3
7 6 8 6
输出样例
11
数学--构造二分
典型题，首先将a和b分别排序，第k值一定在a[1]+b[1]和a[n]+b[m]之间，二分区间求最小的x使得f(x)>=x，f(x)表示所生成数中小于等于x的数量。求f(x)的方法使用双指针
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
ll k;
int a[N],b[N];
ll f(ll x)
{
int j=m;
ll cnt=0;
for(int i=1;i<=n;++i)
{
while(j&&(ll)a[i]+b[j]>x) j--;
cnt+=j;
}
return cnt;
}
ll bina(ll mi,ll ma)
{
ll l=mi,r=ma,ans=r;
while(l<=r)
{
ll mid=(l+r)>>1;
ll tmp=f(mid);
if(tmp>=k) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=m;++i) cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
cout<<bina((ll)a[1]+b[1],(ll)a[n]+b[m])<<'\n';//注意此处的换行
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}