WARush

SRMの結果とか、解けた問題のコードを書いていきます

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 );
    }
}