Codeforces #171 Div2 B "Books"

問題

休憩中に図書館に本を読みに来た。
図書館に本はN冊あり、それぞれ1からNまでの番号が振られている。
また、i番目の本を読み終わる時間はA(i)として分かっている。

i番目の本から読み始めたとすると、
その後i, i+1, i+2・・と読んでいく事にする。

休憩時間Tが与えられた時、
最大何冊の本を読み終えることが出来るかを返せ。

制約

1 <= N <= 10^5
1 <= T <= 10^9
1 <= A(i) <= 10^4

考えた事（勘違い）

i番目の本を読んだ時、次はi+1かi+2の本が読めるのか。
DPっぽいなこれは。

でもNが大きすぎてどうしても計算量が間に合わない
O(N^2)くらいになっちゃう。

i+1かi+2までしか読めないことをなんとか利用できないか？
・・・
だめだ、計算量10憶ぐらいいってまうわ

A <= 10^4・・・
これか？これを使うのか？

ちくしょう・・・問題Bなのに結構むずかしいなぁ・・・

事後

しゃくとり法って実装むずいな～

torus711さんの記事を参考にしました。m(_ _)m

ソースコード

const int MAX_N = 100000;
int a[MAX_N+1];

int main() {
    istream& in = cin;
    
    int n, t;
    in >> n >> t;
    
    for( int i = 1; i <= n; i++ ){
        in >> a[i];
    }
    
    int res = 0, l = 1, r = 1, sum = 0;
    while( r <= n ){
        while( r <= n && sum + a[r] <= t ){
            sum += a[r++];
        }
        res = max( res, r - l );
        sum -= a[l++];
    }

    cout << res << endl;
}