HDU 2795 Billboard(线段树)

来源:岁月联盟 编辑:exp 时间:2012-11-09


题目大意:
给一个h*w的公告牌,h是高度,w是宽度,一个单位高度1为一行,然后会有一些公告贴上去,公告是1*wi大小的长纸条,优先贴在最上面并且最左边的位置,如果没有空间贴得下,就输出-1,可以的话,就输出所贴的位置(第几行)。

分析与总结:
叶节点【x,x】表示board的第x行还可以放置的长度,区间【a,b】表示第a行到b行中剩下空间最大的那一行是多少,如果要把长w的公告放入board时就是update,优先往左子树走(如果左子树的空间足够的话),一直走到叶节点,更新这个叶节点剩下的长度,然后再向上更新。

由于h最大为10^9, 一开始时没注意,建树直接build(1,1,h),结果RE了好多次。其实n最大才20W,所以h组多也只需要用到20W,只需要取min(h,n)即可。

代码:
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#define lson(x) ((x)<<1) 
#define rson(x) (lson(x)|1) 
using namespace std; 
 
const int MAX_NODE = 300000<<2; 
int h,w,n,pos; 
 
struct node{ 
    int left,right,val; 
    int mid(){return (left+right)>>1;} 
    bool buttom(){return left==right;} 
}; 
 
class SegTree{ 
public: 
    void build(int cur,int left,int right){ 
        t[cur].left  = left; 
        t[cur].right = right; 
        if(left==right){ 
            t[cur].val = w; 
            return; 
        } 
        int m = t[cur].mid(); 
        build(lson(cur),left,m); 
        build(rson(cur),m+1,right); 
        push_up(cur); 
    } 
    void update(int cur, int data){ 
        if(t[cur].buttom()){ 
            pos = t[cur].left; 
            t[cur].val -= data; 
            return; 
        } 
        if(t[lson(cur)].val >= data)  
            update(lson(cur),data); 
        else if(t[rson(cur)].val >= data) 
            update(rson(cur),data); 
        push_up(cur); 
    } 
     
private: 
    void push_up(int cur){ 
        t[cur].val = max(t[lson(cur)].val, t[rson(cur)].val); 
    } 
private: 
    node t[MAX_NODE]; 
}; 
 
SegTree st; 
 
int main(){ 
    int x; www.2cto.com
    while(~scanf("%d%d%d",&h,&w,&n)){ 
        st.build(1,1,min(h,n)); 
        for(int i=0; i<n; ++i){ 
            pos = -1; 
            scanf("%d",&x); 
            if(x>w){ 
                puts("-1"); 
                continue; 
            } 
            st.update(1,x); 
            printf("%d/n",pos); 
        } 
    } 
    return 0;