Billboard (HDU 2795)

注意到每个广告的长度是1，因此可以将每这一张广告牌当成一个数列表示，每个初始值为w。使用线段树维护这个数列，每次查询为找到这个数列第一个大于等于x的位置，每次修改操作为将找到的位置值-x

线段树功能：区间查询+单点更新

#include <cstdio>

#include <utility>

#include <queue>

#include <cstring>

#define scan(x) scanf("%d",&x)

#define scan2(x,y) scanf("%d%d",&x,&y)

#define lson rt<<1,l,mid

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

#define root 1,1,h

using namespace std;

const int Max=2e5+10;

int sum[Max<<2];

int h,w,n;

void Pushup(int rt)

{

    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);

}

void Build(int rt,int l,int r)

{

    if(l==r)

    {

        sum[rt]=w;

        return;

    }

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

    Build(lson);

    Build(rson);

    Pushup(rt);

}

int Query(int x,int rt,int l,int r)

{

    if(l==r)

    {

        sum[rt]-=x;

        return l;

    }

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

    if(sum[rt<<1]>=x) ret=Query(x,lson);

    else ret=Query(x,rson);

    Pushup(rt);

    return ret;

}

int main()

{

    while(~scanf("%d%d%d",&h,&w,&n))

    {

        if(h>n) h=n;

        Build(root);

        int x;

        for(int i=0;i<n;i++)

        {

            scan(x);

            if(sum[1]<x) printf("-1\n");

            else

            {

                printf("%d\n",Query(x,root));

            }

        }

    }

    return 0;

}

巴特西

Billboard (HDU 2795)

Billboard (HDU 2795)

最新文章

热门文章