1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | /****************************************************************
* Description:
* Author: Alex Li
* Date: 2023-08-19 17:50:42
* LastEditTime: 2023-09-13 06:58:15
****************************************************************/
#include <iostream>
using namespace std;
int a1[1001],a2[1002];
int solve(int *a1, int *a2, int n, int k) {
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2) {
int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = m1+m2; //空1，cnt是取两个数组的mid之和
//见图解
if (a1[m1]<=a2[m2]) { //空2，根据if内的语句判断
if (cnt < k) left1 = m1 + 1;
else right2 = m2 - 1;
} else {
if (cnt < k) left2 = m2 + 1;
else right1 = m1 - 1;
}
}
if (left1>right1) { //空3，意味着a1数据都找完了
if (left1 == 0) { //说明k不在a1数组里
return a2[k - 1]; //要找到k在a2数组里
} else { //如果left1不等于0，说明a数组两分查找，第k个元素中有一部分在a数组里
int x = a1[left1 - 1], y=a2[k-left1-1]; //空4，查找的k一部分在a1，一部分在a2
return std::max(x, y); //哪个值大选哪个。
}
} else {
if (left2 == 0) {
return a1[k - 1];
} else {
int x = a2[left2 - 1], y=a1[k-left2-1]; //空5，同理空4
return std:: max(x, y);
}
}
}
int main(){
int n,k;
cin>>n>>k;
for (int i = 0; i <n; i++){
cin>>a1[i];
}
for (int i = 0; i <n; i++){
cin>>a2[i];
}
cout<<solve(a1,a2,n,k);
}
|
