HDU2795 Billboard（Dec. 20th, 2018）

线段树

题目来源

题意：有一个长为$h$，宽为$w$的公告板，现在要往上面贴$n$条长度为$k_i$，宽度为1的公告，每个公告必须横着贴，且必须贴在尽量靠左上的位置。求每个公告所贴的行号，若无法贴上，输出-1。

思路：统计每行剩余空间，线段树维护区间最大值，与模板相比略有变形

代码：

// La Lune
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 5;
int t[N << 2];
int h, w, n, Ir;
void pushup(int u){
    t[u] = max(t[u << 1], t[u << 1 | 1]);
}
void build(int u, int l, int r){
    if(l == r){
        t[u] = w;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void query(int u, int l, int r, int len){
    if(l == r){
        if(t[u] >= len){
            t[u] -= len;
            printf("%d\n", l);
            Ir = 1;
        }
        return;
    }
    int mid = l + r >> 1;
    if(t[u << 1] >= len) query(u << 1, l, mid, len);
    else if(t[u << 1 | 1] >= len) query(u << 1 | 1, mid + 1, r, len);
    pushup(u);
}
int main(){
    while(~scanf("%d %d %d", &h, &w, &n)){
        if(h > n) h = n;
        build(1, 1, h);
        for(int i = 1; i <= n; i++){
            Ir = 0;
            int len; scanf("%d", &len);
//          printf("ans = ");
            query(1, 1, h, len);
            if(!Ir) printf("-1\n");
        }
    }
    return 0;
}

反思：
1. 代码很裸，但是需要学习这种转化方式。
2. 做过的题要时常复习，不要把写题解形式化。