【和大于k最小长度连续子序列】 Subsequence

传送门

题意

给定长度为(N)的序列(a_{0},a_{1},dots,a_{n-1})以及整数(S),求出和不小于(S)的连续子序列的长度的最小值，如果解不存在输出(0)

数据范围

(10 < n < 10^{5})
(0< a_{i}leq 10^{4})
(S<10^{8})

题解

用两个指针，st和ed初始都指向序列的初始位置，然后只要和(< S)且未到达序列尾，ed就向后移动，当不能满足和(>=S)时退出，
满足和(< S)时每次st向前移动一次，取得满足条件的最小值即可，ed和st最多移动(2n)次，所以时间复杂度是(O(n))的

Code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fi first
#define se second 
#define ll long long
#define pb push_back
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef double db;
const ll mod=1e9+7;
ll powmod(ll a,ll b,ll p){ll res=1;a%=p;while(b){if(b&1) res=res*a%p;a=a*a%p;b>>=1;}return res;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
const int N=1e5+10;
int n,s;
int seq[N];
int _;
int main(){
    for(scanf("%d",&_);_;_--){
        scanf("%d%d",&n,&s);
        rep(i,0,n) scanf("%d",&seq[i]);
        int st=0,ed=0,sum=0;
        int ans=1e7;
        for(;;){
            while(ed<n && sum<s)
                sum+=seq[ed++];
            if(sum<s) break;
            ans=min(ans,ed-st);
            sum-=seq[st++];
        }
        if(ans>n)
            ans=0;
        printf("%d
",ans);
    }
}