AcWing 800. 数组元素的目标和
原题链接
简单
作者:
sailor
,
2021-03-22 22:58:04
,
所有人可见
,
阅读 263
/*
考虑到题目中给到的单调性,随着i的增大,a[i]越来越大,j是不可能变大的!!
因为b[j]是倒着来的,j应该是越来越小的,我们对于每个i,找到a[i]+b[j]>k的最小的j
然后当i增加的时候,j只能减少或者不变
总的时间复杂度O(n+m)
*/
#include<iostream>
using namespace std;
const int N=100010;
int k, n, m;
int main()
{
cin>>n>>m>>k;
int a[N], b[N];
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=m; i++) scanf("%d", &b[i]);
for(int i=1, j=m; i<=n; i++)
{
while(j>0 && a[i]+b[j]>k) j--;
if(a[i]+b[j]==k)
{
printf("%d %d", i-1, j-1);
break;
}
}
return 0;
}