POJ-3061【尺取算法】

参考思路：传送门

题意

• 链接：POJ-3061
• 给长度为n的数组和一个整数m，求总和不小于m的连续子序列的最小长度

解题思路

• 过程大致分为四步：

1. 初始化左右端点，即先找到一个满足条件的序列。
2. 在满足条件的基础上不断扩大右端点。
3. 如果第二步无法满足条件则终止，否则更新结果。
4. 扩大左端点，并且回到第二步。

• 举个例子：
  n = 10，m = 15
  5 1 3 5 10 7 4 9 2 8
  则ans=2

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int t,n,s,a[maxn];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&s); 
		for(int i=0;i<n;i++)scanf("%d",&a[i]);
		int l=0,r=0,ans=n+1,sum=0;
		while(1)
		{
			while(r<n&&sum<s)sum+=a[r++];
			if(sum<s)break;
			ans=min(ans,r-l);
			sum-=a[l++];
		}
		if(ans==n+1)printf("0\n");
		else printf("%d\n",ans);
	}
	return 0;
}