Subsequence

TimeLimit:1000MS MemoryLimit:65536K

64-bit integer IO format:%lld

Problem Description

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.

Input

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.

Output

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

SampleInput

2

10 15

5 1 3 5 10 7 4 9 2 8

5 11

1 2 3 4 5

SampleOutput
2
3

思路：题目的意思就是给定长度为n的整数数列以及整数S，求出总和不小于S的连续子序列的长度的最小值，如果解不存在，输出0.

个人对尺取的看法：当a1，a2，a3满足条件>=S的时候，我们得到区间长度为3，去掉第一个元素a1，我们在判断a2，a3是否符合条件，如果满足，区间长度更新为2，如果不满足，就将尾部向后扩展，判断a2，a3，a4是否符合，如果符合区间长度更新为3，如果不符合就再向后扩展，一直重复这个操作。

所以我们就用尺取法，先找到总和不小于S的区间，然后用ans去记忆符合条件的区间长度，然后再找符合符合总和不小于S的区间，然后用这个新区间的长度跟ans比较，比ans小就赋值，周而复始，一直到区间走到数组的最后一个为止，就可以了；

晒上核心代码

(i<N&&sum<S;i++)

            sum+=a[i];

            if(sum<S)

                break;

            ans=ans<i-s?ans:i-s;

            sum-=a[s++];

巴特西

16级第一周寒假作业F题

Subsequence

最新文章

热门文章