acwing_800_数组元素的目标和

墨蓝 2021-11-17 02:58 160阅读 0赞

800. 数组元素的目标和

*  [ 题目][Link 1]
 *  [ 提交记录][Link 2]
 *  [ 讨论][Link 3]
 *  [ 题解][Link 4]

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。  
请你求出满足A\[i\] + B\[j\] = x的数对(i, j)。

数据保证有唯一解。

#### 输入格式 ####

第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。

第二行包含n个整数，表示数组A。

第三行包含m个整数，表示数组B。

#### 输出格式 ####

共一行，包含两个整数 i 和 j。

#### 数据范围 ####

数组长度不超过100000。  
同一数组内元素各不相同。  
1≤数组元素≤1091≤数组元素≤109

#### 输入样例： ####

4 5 6
    1 2 4 7
    3 4 6 8 9

#### 输出样例： ####

1 1
    
    
    思想：这到题目需要用到双指针的算法，用一个指针i指向数组a，用另一个指针j指向数组b，我们需要找到的是当a[i] +  a[j] = x 的i与j
    那么当我们找到i对应的j的范围(a[i] + b[j] < x )为【1,di]时，那么i + 1 指针所对应的j也一定在[1,di]这个范围类，所以当我们去寻找j的时候
    可以使用二分去找，这样我们算法的总体的时间复杂度就为：nlogn，
    AC代码：

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int maxn = 1e5 + 5;
    int a[maxn], b[maxn];
    
    inline void read(int &w) {
         char c = getchar();
         w = 0;
         int reg = 1;
         while(c < '0' || c > '9') {
             if(c == '-') reg = -1;
             c = getchar();
         }
         while(c >= '0' && c <= '9') {
             w = w * 10 + c - '0';
             c = getchar();
         }
         
        w *= reg;
    }
    
    inline int binary_sort(int l, int r, int x, int y) {
        while(l < r) {
            int mid = (l + r + 1) / 2;
            if(x + b[mid] <= y) l = mid;
            else r = mid - 1;
        }
        
        return l;
    }
    
    int main(void) {
    //    freopen("in.txt", "r", stdin);
        
        register int n, m, x;
        read(n), read(m), read(x);
        for(int i = 1; i <= n; i ++) read(a[i]);
        for(int i = 1; i <= m; i ++) read(b[i]);
        
        int i = 1, j = 1, di = m, x1, x2, flag = 0;
        for(i = 1; i <= n; i ++) {
            int tmp = binary_sort(1, di, a[i], x);
            if(a[i] + b[tmp] == x) { x1 = i, x2 = tmp; break; }
            else di = tmp;
        }
        
        printf("%d %d\n", x1 - 1, x2 - 1);
        
        
    //    fclose(stdin);
        return 0;
    }

转载于:https://www.cnblogs.com/phaLQ/p/11106009.html

[Link 1]: https://www.acwing.com/problem/content/description/802/
[Link 2]: https://www.acwing.com/problem/content/submission/802/
[Link 3]: https://www.acwing.com/problem/content/discussion/index/802/1/
[Link 4]: https://www.acwing.com/problem/content/solution/802/1/