题目描述

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

输入描述:

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

输出描述:

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
示例1

输入 

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

输出 

2
3

题意

给定若干数和一个目标值，要在这若干数内找到一个连续的区间和要使得这个区间和大于等于目标值，并且要保证这个区间长度最小，并给出这个长度。

思路

这道题具有单调性，同一个起点，终点越远(区间长度越长)，区间和越大。双指针算法，找到第一个大于等于目标值的区间，并逐渐缩短左端点，最后重复这一过程，每次取最小值即可。

代码 

//Subsequence(双指针) 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;

int a[N];

int main()
{
	int t;
	scanf("%d" , &t);
	
	while(t--)
	{
		int n , s;
		scanf("%d %d" , &n , &s);
		
		for(int i = 0 ; i < n ; i++)
			scanf("%d" , &a[i]);
		
		int l = 0 , r = 0 , sum = a[0] , len = n + 1;
		while(l <= r)
		{
			while(sum < s && r + 1 < n)
				sum += a[++r];
							
			while(sum - a[l] >= s)
				sum -= a[l++];
			
			if(sum >= s)
				len = min(len , r - l + 1);
			//cout<<l<<" "<<r<<" "<<sum<<" "<<len<<endl;
			
			sum -= a[l++];	
		}
		
		if(len != n + 1)
			printf("%d\n" , len);
		else
			printf("0\n");
	}
	return 0; 
}