尺取法就是形如一把尺子的方法,一块一块地截取你所需要的序列

题目:给定一个长度位n的序列a1, a2…an以及一个整数s,求不小于s的连续子序列的和的最小值,答案保证该解存在

例如:
input
n = 10, s = 15
a = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8}
--------------------------------------------序列和(>=15)—序列长度–序列长度min值
第一次尺取:(5 1 3 5 10)7 4 9 2 8------24----------------5------------5
第二次尺取:5 (1 3 5 10)7 4 9 2 8------19----------------4------------4
第三次尺取:5 1 (3 5 10)7 4 9 2 8------18----------------3------------3
第四次尺取:5 1 3 (5 10)7 4 9 2 8------15----------------2------------2
第五次尺取:5 1 3 5 (10 7)4 9 2 8------17----------------2------------2
第六次尺取:5 1 3 5 10 (7 4 9)2 8------20----------------3------------2
第七次尺取:5 1 3 5 10 7 (4 9 2)8------15----------------3------------2
第八次尺取:5 1 3 5 10 7 4 (9 2 8)-----19----------------3------------2

这实际上就是一个双指针算法的应用

我们总结一下具体做法:
1.初始化指针i = j = 0,让i,j维护一段合法的区间(在这道题目中,就是维护一段和不超过s的序列)
2.让j往后挪动,获得合法区间
3.让i跟在j的后面移动,获取更小的区间
4.如果所有的区间都不合法,那么就跳出循环

由于整个区间只会被遍历一遍,所以时间复杂度是O(n)

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
//#define DEBUG
#define RI register int
#define ULL unsigned long long
#define PII pair<int, int>
#define fi first
#define se second
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define PI acos(-1.0)
using namespace std;
const int N = 1e5 + 10;
int n, s, a[N];

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    printf("Time cost : %lf s\n", (double)clock() / CLOCKS_PER_SEC);
#endif
    IOS
    cin >> n >> s;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int ans_min = 0x3f3f3f3f, ans_max = -1;
    for (int i = 0, j = 0, sum = 0; i < n;)
    {
        while(sum < s && j < n)
            sum += a[j++];
        if(sum < s)
            break;
        ans_min = min(ans_min, j - i);
        ans_max = max(ans_max, j - i);
        sum -= a[i++];
    }
    cout << ans_min << ' ' << ans_max << '\n';
}