首页 > 代码库 > POJ 3061 Subsequence(Two Pointers)

POJ 3061 Subsequence(Two Pointers)

 

【题目链接】 http://poj.org/problem?id=3061

 

【题目大意】

  给出S和一个长度为n的数列,问最短大于等于S的子区间的长度。

 

【题解】

  利用双指针获取每一个恰好大于等于S的子区间,更新答案即可。

 

【代码】

#include <cstdio>int T,a[100005];int main(){    scanf("%d",&T);    while(T--){        int n,S,s,h,t,ans;        scanf("%d%d",&n,&S);ans=n;        for(int i=1;i<=n;i++)scanf("%d",&a[i]);        for(int i=1,j=1;i<=n;i++){            s+=a[i];            if(s>=S){                ans=min(ans,i-j);                s-=a[j++];            }        }printf("%d\n",ans);    }return 0;}

  

POJ 3061 Subsequence(Two Pointers)