HDU 2795 Billboard(线段树)
题目大意:
给一个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.zzzyk.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;
}
补充:软件开发 , C++ ,