## poj 3061 尺取法 原

Loi_DL

Subsequence
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 12078 Accepted: 5055

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.

Sample Input

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

Sample Output

``````2
3``````

Source

ps：尺取法是需要序列符合单调性的。

，来求满足条件的最小区间的方法称为尺取法。

#include <iostream>
#include <cstdio>
using namespace std;
int a[100050];
int main()
{
int t;
cin>>t;
while (t!=0)
{

t--;
int n,s;
cin>>n>>s;
for(int i=1;i<=n;i++)
cin>>a[i];
int sum=0,q=1,e=1,ans=n+1;

for(;;)
{
while(e<=n&&sum<s)
{
sum+=a[e];
e++;
}
if(sum<s)
break;
ans=min(ans,e-q);
sum-=a[q];
q++;
}
if(ans==n+1)
cout<<0<<endl;
else
cout<<ans<<endl;
}
return 0;
}

### Loi_DL

BZOJ：2038: [2009国家集训队]小Z的袜子(hose)（莫队算法模板）

GoldenFingers
2018/08/06
0
0
LeetCode-Longest Substring Without Repeating Characters

2018/04/02
0
0
LeetCode 滑动窗口法总结

dby_freedom
04/07
0
0
POJ 1067 取石子游戏

angel_kitty
2017/02/19
0
0
poj1067:取石子游戏（Betty定理）

qq_35649707
2017/12/22
0
0

27分钟前
0
0
Jenkins系列_插件安装及报错处理

shzwork

2
0
mysql mysql的所有查询语句和聚合函数（整理一下，忘记了可以随时看看）

edison_kwok

9
0

4
0

3
0