POJ 3061 Subsequence（尺取法）-蒲公英云

POJ 3061 Subsequence（尺取法）

梦里梦外; 2022-06-16 07:24 310阅读 0赞

Subsequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 14595 Accepted: 6146
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

题解：求连续数列的和大于等于给定值S，数列最短的长度。最近学了一个新算法尺取法可以拿来练手

核心代码：

int l = 0, sum = 0, w = 0,flag = 0;
        while(l < n){
            while(w < n && sum < m){
   //从前面开始
                sum += a[w];
                w++;
            }
            if(sum == m){
   //满足条件
                flag = 1;
                break;
            }
            sum -= a[l];//尺取法前进
            l++;
        }

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 200005;
int N,S;
int a[maxn];
int chiqu()
{
    int i=0;
    int j=0;
    int sum=0;
    int res=2*N;
    for(;;)
    {
        while(j<N&&sum<=S)
            sum+=a[j++];
        if(sum<S)
            break;
        res=min(j-i,res);
        sum -=a[i++];
    }
    if(res>N)
        res=0;
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>N>>S;
        for(int i=0;i<N;i++)
            cin>>a[i];
        cout<<chiqu()<<endl;
    }
    return 0;
}