首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。