一、题目描述
给定两个升序排序的有序数组 A AA 和 B BB,以及一个目标值 x xx。
数组下标从 0 00 开始。
请你求出满足 A [ i ] + B [ j ] = x A[i]+B[j]=xA[i]+B[j]=x 的数对 ( i , j ) (i,j)(i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n , m , x n,m,xn,m,x,分别表示 A 的长度,B 的长度以及目标值 x。
第二行包含 n nn 个整数,表示数组 A。
第三行包含 m mm 个整数,表示数组 B。
输出格式
共一行,包含两个整数 i ii 和 j jj。
数据范围
数组长度不超过 1 0 5 10^510
5
。
同一数组内元素各不相同。
1 ≤ 1≤1≤ 数组元素 ≤ 1 0 9 ≤10^9≤10
9
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
1
2
3
输出样例:
1 1
————————————————
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
int main()
{
scanf("%d %d %d", &n, &m, &x);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i++){
scanf("%d", &b[i]);
}
for(int i = 1, j = m; i <= n; i++){
while(j >= 1 && a[i] + b[j] > x){
j--;
}
if(a[i] + b[j] == x){
printf("%d %d\n", i - 1, j - 1);
return 0;
}
}
return 0;
}