Codeforces #182 Div2 B "Eugeny and Play List"
問題
http://codeforces.com/contest/302/problem/B
訳
ユージャニーは音楽を聴くのが好きである。
彼はプレイリストにn個の曲を入れている。
i番目の曲の長さはt_i分である事が分かっている。
ユージャニーはそれぞれの曲を複数回聴くこともあり、彼はi番目の曲をc_i回聴く。
ユージャニーのプレイリストの構成は次のようになっている。
最初、1番目の曲がc_1回再生され、次に2番目の曲がc_2回再生され・・・
最後のn番目の曲がc_n回再生される。
ユージャニーは彼が好きな曲がm分目に再生されている、ということをいくつかメモしておいた。
今、彼はそれぞれのmについて、それがプレイリストの何番目の曲なのか、と言う事を知りたい。
それぞれのmについて、それが何番目の曲であるかを出力せよ
制約
1 <= n, m <= 10^5
考えた事
各曲が何分目に終わるのかということを出しておいて、
それぞれのmで二分探索する。
事後
何曲目まで調べたか覚えておけば、O(N + M) = O(N)でいけるなぁ・・
頭いいなぁ・・
まあ二分探索の練習ということで
ソースコード
int a[100050]; int main() { int N, M; cin >> N >> M; a[0] = 0; for( int i = 1; i <= N; i++ ){ int c, t; cin >> c >> t; a[i] = a[i-1] + c * t; } for( int i = 0; i < M; i++ ){ int mo; in >> mo; int l = 1; int r = N; while( l <= r ){ int m = (r + l) / 2; if( a[m] == mo ){ l = m; break; }else if( a[m] < mo ){ l = m + 1; }else{ r = m - 1; } } printf( "%d\n", l ); } }