c++题目_第K小的数(进阶)
第K小的数
时间限制:
C/C++ 1s
其他语言 2s
空间限制:
C/C++ 256MB
其他语言 512MB
题目描述
给定 nn 个正整数 a1,a2,…,ana1,a2,…,an 和 mm 个正整数 b1,b2,…,bmb1,b2,…,bm。
请在 n×mn×m 个 ai+bj(1≤i≤n,1≤j≤m)ai+bj(1≤i≤n,1≤j≤m) 中,找到第 kk 小的数(不去重)。
输入描述
第一行包含一个正整数 T(1≤T≤10)T(1≤T≤10),表示测试数据的组数。
每组数据第一行包含三个正整数 n,m,k(1≤n,m≤100000,1≤k≤n×m)n,m,k(1≤n,m≤100000,1≤k≤n×m)。
第二行包含 nn 个正整数 a1,a2,…,an(1≤ai≤108)a1,a2,…,an(1≤ai≤108)。
第三行包含 mm 个正整数 b1,b2,…,bm(1≤bi≤108)b1,b2,…,bm(1≤bi≤108)。
输出描述
对于每组数据输出一行一个整数,即第 kk 小的数。
测试样例1
输入
1
3 4 7
5 4 3
7 6 8 6
输出
11
代码:
#include
using namespace std;
int a[99999];
int b[99999];
int main() {
int t;
cin >> t;
for (int i = 0; i > n >> m >> k;
for (int j = 0; j > a[j];
}
for (int j= 0; j > b[j];
}
sort(a, a + n);
sort(b, b + m);
int left = a[0] + b[0];
int right = a[n - 1] + b[m - 1];
while (left <= right) {
int mid = left + (right - left) / 2;
int sum= 0;
int i = 0, j = m - 1;
while (i = 0) {
if (a[i] + b[j] = k) {
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << left << endl;
}
return 0;
}