尺取法

Subsequence

题意：

给你长度为n的序列，找一个连续子序列的和大于等于s，问该子序列的长度最短为多少

思路：

尺取法

用两个变量来代替尺子的两端，我用i代替左端，j代替右端

最开始序列和sum小于s，就让sum加上tr[j]，并让j++

当sum-tr[i]大于等于s时，说明序列删一个元素，得到的子序列还满足大于等于s，就更新最小值，进行循环

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 150000 + 5
typedef  long long ll ;

inline int IntRead(){
    char ch = getchar();int s = 0, w = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();}
    while(ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
int tr[MAX];
int main()
{
    int n, t, s;
    cin>>t;
    while (t--) {
        cin>>n>>s;
        for(int i = 1; i <= n; ++i){
            cin>>tr[i];
        }
        int  i = 1, sum = 0, minx = 1e9;
        for(int j = 1; j <= n; ++j){
            sum += tr[j];
            while (sum - tr[i] >= s) {
                sum -= tr[i];
                i++;
                minx = min(minx, j - i + 1);
            }
        }
        if(minx == 1e9)//如果没有能让sum大于s的，则minx就不会更新，输出0即可
            cout<<0<<endl;
        else
            cout<<minx<<endl;
    }
    return 0;
}