题意:
给一个升序数列和一个降序数列,判读是否能从中各取一个数,使他们的和为10000.
思路:
尺取法是一种求最小区间的算法,通过设置不前移的指针p和不后移的指针q来求满足某个条件的最小区间。类似地,设置两个不前移的指针p,q,可设计O(n)算法。
代码:
//poj 2366
//sep9
#include<iostream>
using namespace std;
const int maxN=40000;
int a[maxN],b[maxN];int main()
{int n,m;while(scanf("%d",&n)==1){int i;for(i=0;i<n;++i)scanf("%d",&a[i]);scanf("%d",&m);for(i=0;i<m;++i)scanf("%d",&b[i]);int p=0,q=0;int ans=0;while(p<n&&q<m){if(a[p]+b[q]==10000){ans=1;break;}else if(a[p]+b[q]<10000)++p;else++q;}printf("%s\n",ans==0?"NO":"YES");}return 0;
}