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なのに結構むずかしいなぁ・・・
ソースコード
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; }