AcWing 800. 数组元素的目标和(二分解法)
原题链接
简单
作者:
夏凉浮生半城雪
,
2021-07-18 10:50:23
,
所有人可见
,
阅读 210
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <string>
#include <queue>
#include <vector>
#include <utility>//pair
#include <cmath>
#include <limits.h>//INT_MAX INT_MIN
typedef long long ll;
using namespace std;
const int ma = INT_MAX;
const int num = 1e5+5;
int a[num],b[num];
bool fin(int i,int m,int x){
int l=0,r=m-1;
while(l<r){
int mid= l+r >>1;
if(a[i]+b[mid]>=x) r=mid;
else l=mid+1;
}
if(a[i]+b[r]==x){
printf("%d %d\n",i,r);
return true;
}
else
return false;
}
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<m;i++)
scanf("%d",&b[i]);
int s=0;
for(int i=0;i<n;i++){
if(a[i]+b[m-1]<x||a[i]+b[0]>x)
continue;
else if(fin(i,m,x)){
break;
}
}
return 0;
}