} } }

    codeforces 302B - Eugeny and Play List

    添加时间:2013-6-3 点击量:

    二分查找。。。


    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include <ctype.h>
    #include <math.h>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define ll long long
    #define ls rt<<1
    #define rs ls1
    #define lson l,mid,ls
    #define rson mid+1,r,rs
    #define middle (l+r)>>1
    #define eps (1e-9)
    #define clr_all(x,c) memset(x,c,sizeof(x))
    #define clr(x,c,n) memset(x,c,sizeof(x[0])(n+1))
    #define MOD 1000000007
    #define inf 100000007
    #define pi acos(-1.0)
    #define for(i,a,b) for(int i=(a);i<(b);i++)
    #define M 100000+5
    int n,m;
    int c[M],t[M],sum[M];
    int bSearch(int l,int r,int x){
    if(l+1==r)return r;
    int mid=(l+r)/2;
    if(x>sum[mid])return bSearch(mid,r,x);
    else return bSearch(l,mid,x);
    }
    int main(){
    int i,j,x;
    while(~scanf(%d %d,&n,&m)){
    sum[0]=0;
    for(i,1,n+1){
    scanf(%d %d,&c[i],&t[i]);
    sum[i]=sum[i-1]+c[i]t[i];
    }
    while(m--){
    scanf(%d,&x);
    printf(%d\n,bSearch(0,n,x));
    }
    }
    return 0;
    }

    容易发怒的意思就是: 别人做了蠢事, 然后我们代替他们, 表现出笨蛋的样子。—— 蔡康永
    分享到: