完善程序1解析


 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);
}
Scroll to Top