本文共 1439 字，大约阅读时间需要 4 分钟。

题目大意是:

一开始有一块高为h，宽为w的一块屏幕（一开始的时候屏幕是空的）。

然后有n次询问，每次询问先给你一个wi，代表的是当前第i个广告的宽度（每个广告的高度为1），然后要你输出当前的广告是放在第几行的。

放置的要求为：

首先我们肯定要选较上面的，然后再选较上面的较左边的那个位置。当没有位置放时，那么就输出-1.

这道题一开始我看到这道题的数据范围吓了一跳，10的9次，那建树还不爆了吗。后来网上搜了下题解，发现这里可以优化的，题目中给的m大概是在2万左右，又因为放置广告的最差情况时每行放一个广告，那么也就是说高度的最大值就是每次给出的m和h的较小值。

其他的建树就和普通的线段树是差不多的，如果不能想出来，那么就看看代码找个思路吧。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define maxn 222222int h,w,n;int pos=-1;int a[maxn];struct node{    int l,r,len,des,flag;}tree[maxn*4];void pushup(int v){    int temp=v<<1;    tree[v].len=max(tree[temp].len,tree[temp+1].len);}void build(int v,int l,int r){    tree[v].l=l;    tree[v].r=r;    tree[v].des=0;    tree[v].flag=0;    tree[v].len=w;    if(l==r) return;    int temp=v<<1;    int mid=(l+r)>>1;    build(temp,l,mid);    build(temp+1,mid+1,r);    //pushup(v);}void query(int v,int lj){    if(tree[v].l==tree[v].r&&tree[v].len>=lj){        pos=tree[v].l;        tree[v].len-=lj;        return;    }    int temp=v<<1;    if(lj<=tree[temp].len) query(temp,lj);    else if(lj<=tree[temp+1].len) query(temp+1,lj);    pushup(v);}int main(){    while(~scanf("%d%d%d",&h,&w,&n)){        memset(a,0,sizeof(a));        int gg=min(h,n);        build(1,1,gg);        //for(int i=1;i<=6;i++) printf("%d ",tree[i].len); puts("");        for(int i=1;i<=n;i++){             scanf("%d",&a[i]);             pos=-1;             if(tree[1].len
      
     
    
   

转载地址：https://blog.csdn.net/ACMer_hades/article/details/46565805 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！