题意为在h*w的矩形方块里面贴海报,求出最左边能贴海报的区域的行数。
用PushUp来维护当前可以放海报的最大值。每次贴下之后,就把num值减掉可以贴的值。
注意的一点是,当海报数n比高度h小时,令h=n。
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; #define maxn 200010 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Tree { int l,r,num; }tree[maxn<<2]; int h,n,w; void PushUp(int rt) { tree[rt].num=max(tree[rt<<1].num,tree[rt<<1|1].num); } void build(int l,int r,int rt) { tree[rt].l=l; tree[rt].r=r; tree[rt].num=w; if(tree[rt].l==tree[rt].r) return ; int m=(l+r)>>1; build(lson); build(rson); } int query(int val,int rt) { int l,r; l=tree[rt].l; r=tree[rt].r; if(l==r){ tree[rt].num-=val; return l; } int m=(l+r)>>1; int ret=0; if(tree[rt<<1].num>=val) ret=query(val,rt<<1); else ret=query(val,rt<<1|1); PushUp(rt); return ret; } int main() { while(~scanf("%d%d%d",&h,&w,&n)){ if(h>n) h=n; build(1,h,1); for(int i=1;i<=n;i++){ int q; scanf("%d",&q); if(tree[1].num<q) printf("-1\n"); else{ printf("%d\n",query(q,1)); } } } return 0; }