学步园

这题想清楚了 就很简单。。想不清楚就蛋疼。反正我是蛋疼了2天

给你一块矩阵 高h 宽w

然后给n 个 高 1 宽 x 的小矩阵

按题意放 能不能放下海报

h * w 可以看成 h 个节点每个节点长度为w 

这样小矩阵的高度就可以忽略了 只要考虑x

按题意 贴入海报 其实就是对节点进行删除x长度操作

然后都是从最左边开始找 

父节点存的是子节点 最大长度 

tree[1].v 存的就是所有节点中最大的长度

如果x > tree[1].v 那么就代表 无法贴入海报

在n个海报都可以插入 的情况下， 最坏的情况是每个海报的x = w ,那么最多只需要 n 的节点就可以了

所以当h > n 的时候 只需要n 个节点

如果h <= n 那么最好的情况也只能插入h个

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int const MAXN = 200010;
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
struct Tree{
    int l,r;
    int v;
}tree[MAXN<<2];
void Build(int w,int l,int r,int rt){
    tree[rt].v = w;
    if(l == r) return ;
    int m = (l + r)>>1;
    Build(w,Lson);
    Build(w,Rson);
}
inline int Max(int a,int b){
    return a>b?a:b;
}
inline void PushUp(int rt){
    tree[rt].v = Max(tree[rt<<1].v,tree[rt<<1|1].v);
}
int Query(int w,int l,int r,int rt){
    if(l == r){
        tree[rt].v -= w;
        return l;
    }
    int m = (l + r)>>1;
    int ret = 0;
    if(w <= tree[rt<<1].v) ret = Query(w,Lson);
    else ret = Query(w,Rson);
    PushUp(rt);
    return ret;
}
int main(){
    int h,w,n;
    while(~scanf("%d%d%d",&h,&w,&n)){
        if(h > n) h = n;
        Build(w,1,h,1);
        for(int i = 1;i <= n;i++){
            int x;
            scanf("%d",&x);
            if(tree[1].v < x) printf("-1\n");
            else printf("%d\n",Query(x,1,h,1));
        }
    }
    return 0;
}