常用技巧精选

尺取法

Subsequence

尺取法，使用两个指针，让右边的指针往右走知道找到符合条件的位置，如果找不到就break出while循环，左边的指针每次往右移动一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 2147483647;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,s;
    while(cin>>n>>s)
    {
        vector<int>a(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        int ret=n+1;
        int l=1,r=1;
        ll sum=0;
        while(1){
            while(r<=n&&sum<s)
            {
                sum+=a[r++];
            }
            if(sum<s)break;
            ret=min(ret,r-l);
            sum-=a[l++];    
        }
        if(ret>n)cout<<0<<'\n';
        else cout<<ret<<'\n';
    }    

    return 0;    
}