「POJ3061」Subsequence

题目描述

给定长度为n的数列整数a0,a₁,…,an-1以及整数s。求出总和不小于s的连续子序列的长度的最小值。如果解不存在，则输出0。

输入

题目包含多组数据。

输入的第一行有一个整数T  代表有T组数据。

对于每组数据分为两行：

第一行有两个整数n,s (10<n<100,000,s<100,000,000)。

第二行有n个整数ai (0<ai≤10,000)。

样例输入

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

样例输出

2
3

题解

尺取法。先找到第一段和超过s的连续序列，然后去掉最左边的，再往右延展到第一次超过s，然后再去掉最左边，以此类推，复杂度为o(n)。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int a[100001];
int main()
{
	int t,n,s;
	scanf("%d",&t);
	while(t--)
	{
		int l=1,r=0,sum=0,ans=1e9;
		scanf("%d %d",&n,&s);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		while(1)
		{
			while(r<n && sum < s)
			{
				r++;
				sum+=a[r];
			}
			if(sum<s)
				break;
			ans = min(ans,r-l+1);
			sum-=a[l];
			l++;
		}
		if(ans>n)
			ans=0;
		printf("%d\n",ans);
	}
	return 0;
}