当前位置: 代码迷 >> 综合 >> poj 2366 Sacrament of the sum 尺取法的灵活运用
  详细解决方案

poj 2366 Sacrament of the sum 尺取法的灵活运用

热度:33   发布时间:2024-01-19 06:15:25.0

题意:

给一个升序数列和一个降序数列,判读是否能从中各取一个数,使他们的和为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;	
}