【题目链接】:http://codeforces.com/problemset/problem/589/G

【题意】



有n个人;

每个人每天在开始工作之前,都需要di单位的准备时间,然后才能开始工作;

然后每个人都有m天的时间,每天有ti个单位的时间供每个人进行准备工作以及工作;

也就是说第i个人每天必须要先扣掉di个单位的时间;剩下的才是它能够工作的时间;

然后每个人都需要完成ri个单位的时间的工作量;

然后如果你发现某一天连准备的时间都不够的话,你可以跳过这一天;

问你最早在第几天,第i个人才能够完成ri个单位的时间的工作量;

【题解】



首先把m天的时间按照时间的多少降序排;

然后把n个人,按照ri的大小降序排;

然后顺序枚举n个人;

对于每个人,维护一个指针r,这里1..r对应了哪些天是>=d[i]的;

每次r递增一个,就把它加到树状数组里面,即对应的第id天递增t[i]个单位的时间,同时记录第id天之前有多少天是满足>=d[i]的;

然后二分第i天;

看看

前i天的时间和−前i天>=d[i]天的天数∗d[i]是不是大于等于r[i];

大于等于的话就变小一点,否则变大一点;



【Number Of WA】



0

（C++11不能编译,很奇怪）



【反思】



数据结构题的话,认真想想就好.

不要着急,想好了再动手。



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int M = 2e5;

struct abc{

    int t,id;

};

struct person{

    int d,r,id;

};

struct BIT{

    pll a[M+10];

    int lowbit(int x){

        return x&(-x);

    }

    void add(int x,int y){

        while (x <= M){

            a[x].fi+=y;

            a[x].se+=1;

            x+=lowbit(x);

        }

    }

    LL sum1(int x){

        LL temp = 0;

        while (x > 0){

            temp += a[x].fi;

            x-=lowbit(x);

        }

        return temp;

    }

    LL sum2(int x){

        LL temp = 0;

        while (x > 0){

            temp += a[x].se;

            x-=lowbit(x);

        }

        return temp;

    }

};

int n,m,b[M+10];

abc a[M+10];

person c[M+10];

BIT d;

int main(){

    //Open();

    Close();

    cin >> n >> m;

    rep1(i,1,m){

        cin >> a[i].t;

        a[i].id = i;

    }

    sort(a+1,a+1+m,[&] (abc a,abc b){ return a.t > b.t;});

    rep1(i,1,n){

        cin >> c[i].d >> c[i].r;

        c[i].id = i;

    }

    sort(c+1,c+1+n,[&] (person a,person b) {return a.d > b.d;});

    int cur = 1;

    rep1(i,1,n){

        while (cur<=m && a[cur].t>=c[i].d){

            d.add(a[cur].id,a[cur].t);

            cur++;

        }

        int l = 0,r = m,temp = 0;

        while (l <= r){

            int mid = (l+r)>>1;

            LL temp1 = d.sum1(mid),temp2 = d.sum2(mid);

            temp1-=temp2*c[i].d;

            if (temp1 >= c[i].r){

                temp = mid;

                r = mid - 1;

            }else {

                l = mid + 1;

            }

        }

        b[c[i].id] = temp;

    }

    rep1(i,1,n) cout << b[i] <<' ';

    return 0;

}