3061:Subsequence

keyword

尺取り法　C++

概要

正整数Sと正整数の数列が与えられる(長さは100000以下)。和がS以上になる連続した部分列の最小の長さを求める問題。
プログラミングコンテストチャレンジブックを参考にして解いた。
それとreadint()を自作してみた。やっぱりscanfより早いらしい。
…今気づいた。これ負の数に対応していない。

inline int readint(){
    int ret = 0, x;
    while(x=getchar(), !('0'<=x&&x<='9'));
    ret = x-'0';
    while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + x-'0';
    return ret;
}

int main(){
    int rept;
    rept = readint();
    static int ns[100002];

    while(rept--){
        int i, n, s;
        n = readint();
        s = readint();
        REP(i,n) ns[i] = readint();

        int cur=0, p=0, q=0, ans = n+1;
        while(q<n){
            cur += ns[q++];
            while(cur >= s){
                ans = min(ans, q-p);
                cur -= ns[p++];
            }
        }

        printf("%d\n",(ans<n)?ans:0);
    }

    return 0;
}