Billboard

3 5 5
2
4
3
3
3

1
2
1
3
-1

题解及代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <string>
#define maxn 200010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ALL %I64d
using namespace std;
typedef long long  ll;


struct segment
{
    int l,r;
    int value;
} son[maxn<<2];

void PushUp(int rt)
{
    son[rt].value=max(son[rt<<1].value,son[rt<<1|1].value);
}

void Build(int value,int l,int r,int rt)
{
    son[rt].l=l;
    son[rt].r=r;
    son[rt].value=value;
    if(l==r)
    {
        return;
    }
    int m=(l+r)/2;
    Build(value,lson);
    Build(value,rson);
}


int Query(int w,int rt)
{
    if(son[rt].l==son[rt].r)
    {
        son[rt].value-=w;
        return son[rt].l;
    }

    int m=(son[rt].l+son[rt].r)/2;
    int ret=0;

    if(son[rt<<1].value>=w)
        ret=Query(w,rt<<1);
    else ret=Query(w,rt<<1|1);

    PushUp(rt);
    return ret;
}

int main()
{
    int n,w,t;
    while(scanf("%d%d%d",&n,&w,&t)!=EOF)
    {
        n=min(n,t);      //n的最大值超过我们容忍的范围，但是t却没超过
                         //所以我们取两者更小的那一个
        Build(w,1,n,1);

        for(int i=0; i<t; i++)
        {
            scanf("%d",&w);
            if(son[1].value>=w)
                printf("%d\n",Query(w,1));
            else printf("-1\n");
        }
    }
    return 0;
}
/*
我们使用线段树记录从l到第r行的长度的最大值，
当我们想要插入一个广告就代表我们从黑板的每行中找对应的满足情况的那一行，
那我们可以查看线段树左侧的最大值和右侧的最大值，
当左侧有满足情况的一行时，我们就想做寻找，当没有的时候，就去右侧寻找，
如果两侧都没有，那么我就该输出-1。

当我们找到满足的那一行的时候，我们把当前行的value减去广告的长度，
然后回溯维护整个线段树的最大值区间。
*/

hdu 2795 Billboard（线段树）,布布扣,bubuko.com

hdu 2795 Billboard（线段树）

原文：http://blog.csdn.net/knight_kaka/article/details/38541347