【two points】 数组元素的目标和

传送门

题意

给定两个升序序列(A、B)，以及一个目标值(x)，求出来满足(A_{i} + B_{i} = x)的(（i，j）)数对的数量

数据范围

$1leq N leq 10^{5} $
(1leq A_{i}、B_{i} leq 10^{9})

题解

两个有序的序列，如果满足(A_{i}+B_{j})的两个数的其中一个一定不会和别的组成(x)，利用这点线性扫描

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m,x;
int a[N],b[N];
int main(){
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    for(int i=0,j=m-1;i<n;i++){
        while(j>=0&&a[i]+b[j]>x) j--;
        if(a[i]+b[j]==x) {
            cout<<i<<' '<<j;
            break;
        }
    }
}