POJ 3061 Subsequence（尺取）

题意：
给你一个长度为n的数列，再给你一个数s，让你找出数列中连续元素和>=s的最短长度。
思路：
可以遍历每个数然后二分找右界。复杂度O(nlogn)
尺取法，搞个l和r，没到s时候就一直把r往右推，到了s就把 l 往右推直到小于s。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <iterator>
#include <list>
#include <cstdio>
#include <iomanip>
#include <climits>
#define ll long long
using namespace std;
const ll maxn=(ll)1e5+100;
ll tc,n,s,a[maxn];
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif
    cin>>tc;
    while(tc--){
        cin>>n>>s;
        for(int i=1; i<=n; ++i) cin>>a[i];
        ll ans=LLONG_MAX;
        ll l=1,r=1,sum=0;
        for(;;){
            while(r<=n && sum<s){
                sum+=a[r++];
            }
            if(sum<s) break;
            ans=min(ans, r-l);
            sum-=a[l++];
        }
        if(ans==LLONG_MAX) ans=0;
        cout<<ans<<'\n';
    }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

本文地址：https://blog.csdn.net/qq_43555854/article/details/107895737