MENU

UVa1121/POJ3061 Subsequence

UVa1121

POJ3061

尺取法模板。

#include<cstdio>
#include<cctype>
#include<algorithm>
struct io {
    static const int L = (1 << 21) + 1;
    char obuf[L], *oS, *oT, st[50];
    void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    void putc(char x) {
        *oS++ = x;
        if(oS == oT)flush();
    }
    template<class T>void print(T x) {
        if(!x) { putc('0'); return; }
        int tp = 0;
        for(; x; st[tp++] = x % 10 + 48, x /= 10);
        for(tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N, S, a[100001];
int main() {
    while(scanf("%d%d", &N, &S) == 2) {
        for(int i = 1; i <= N; ++i)scanf("%d", a + i);
        int ans = 100001;
        for(int l = 1, r = 0, cur = 0; l <= N; ans = std::min(ans, r - l + 1), cur -= a[l++]) {
            while(cur < S && r < N) cur += a[++r];
            if(cur < S)break;
        }
        ip.print(ans == 100001 ? 0 : ans), ip.putc('\n');
    }
}