这道题将深度看作高度就可以了。。
struct node { int l,r; int value; } tree[N<<2];
每一个叶子的value就是这一行剩余的格子数
树枝的value是它两个叶子的较大value值，这样方便查找
注意递归
构造一颗树就好
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=200005; struct node { int l,r; int value; } tree[N<<2]; int h,w,n; void build(int i,int l,int r) { tree[i].r=r; tree[i].l=l; tree[i].value=w; if(l==r) return; int mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); } int qurry(int i,int v) { if(tree[i].r==tree[i].l) { tree[i].value-=v; return tree[i].r; } else { int v1=0,v2=0; int mid=(tree[i].l+tree[i].r)/2; if(tree[i*2].value>=v) v1=qurry(i*2,v); else if(tree[i*2+1].value>=v) v2=qurry(i*2+1,v); tree[i].value=max(tree[i*2].value,tree[i*2+1].value); return v1+v2; } } int main() { while(~scanf("%d %d %d",&h,&w,&n)) { if(h>n) h=n; build(1,1,h); int x,ans; for(int i=1; i<=n; i++) { scanf("%d",&x); if(x<=tree[1].value) printf("%d\n",qurry(1,x)); else printf("-1\n"); } } return 0; }
