题意:在一块h*w的公告板上,每次贴上1*wi的横条,规则是每次必须贴在目前可以贴的地方中最上且最左的位置,输出每次贴在第几行。
思路:data[i]中记录第i行剩下多少空间可贴,每次寻找最小的i,满足data[i]>=wi即可。然后更新data[i]=data[i]-w[i]。
直接顺序查找data[i]无疑是超时的,这里可以考虑使用线段树,单点更新记录最大值。
具体的方法是:初始化所有节点data[x]=w。
首先,如果根节点所代表的区间内最大值<w (即maxv[1]<w),直接输出-1。
否则,对于每次递归到的的根节点,如果maxv[ls]>=wi,则往左儿子递归,不然往右儿子递归。直到找到区间长度为1的区间,这个位置就是这次贴公告的地方。更新这个位置的data值,维护线段树。
注意:因为n最大到20w,所以维护20w个data[]点即可
个人认为这个方法特别神奇,二叉查找必须在单调区间内进行,而这个方法可以在非单调区间内进行类似lower_bound的操作。
(这个代码里我把query和update写在一起了)
#include<cstdio> #define MAXN 200005 #define M ((L+R)>>1) #define ls o<<1 #define rs o<<1|1 #define lson ls,L,M #define rson rs,M+1,R int max(int a,int b) {return a>b? a:b;} int maxv[MAXN*3],h,w,n,p,v; void pushup(int o) {maxv[o]=max(maxv[ls],maxv[rs]);} void build(int o,int L,int R) { if(L==R) {maxv[o]=w;return;} build(lson); build(rson); pushup(o); } void query(int o,int L,int R) { if(L==R) {maxv[o]-=v;printf("%d\n",L);return;} maxv[ls]>=v? query(lson):query(rson); pushup(o); } int main() { while(~scanf("%d%d%d",&h,&w,&n)) { if(h>n) h=n; build(1,1,h); for(int i=0;i<n;++i) { scanf("%d",&v); if(maxv[1]<v) printf("-1\n"); else query(1,1,h); } } return 0; }