欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

子序列(尺取入门)

程序员文章站 2022-06-06 15:22:48
...

 

大神的图片 帮助理解这个题的过程
子序列(尺取入门)

经典例题:

给出了n个正整数序列(10<n<100,000),它们均小于或等于10000,正整数s(s<100 000 000)。编写一个程序来查找序列的连续元素的子序列的最小长度,其总和大于或等于S。

输入

第一行是测试用例的数量。对于每个测试用例,程序必须从第一行读取由间隔分隔的数字n和s。序列的数目在测试用例的第二行中给出,由间隔分隔。输入将以文件结尾完成。

产量

对于每种情况,程序都必须在输出文件的单独行上打印结果。如果没有答案,请打印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

代码:

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