HDU2795 Billboard（线段树）

March 05, 2016

题目链接

题意：高为 h，宽为 w 的广告板，往上面贴一些宽都是 1 的广告。要求尽量往上和往左贴，输入能贴在第几行，如果都贴不上输出-1.

首先取 min（h，n）作为线段树长度，因为最坏情况是 n 个广告每个一行，如果 h>n 的话剩下的肯定贴不了。

用线段树来维护 1~h 中剩余长度的最大值，利用其由上而下搜索和先遍历左子树的特性，找到广告板上最上面符合条件的行数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 200005;
int tree[maxn<<2];
int h, w, n;

void pushUp(int rt){
    tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
}

void build(int l, int r, int rt){
    if(l == r){
        tree[rt] = w;
        return;
    }
    int m = l+(r-l)/2;
    build(lson);
    build(rson);
    pushUp(rt);
}

int query(int num, int l, int r, int rt){
    if(l == r){
        tree[rt] -= num;
        return l;
    }
    int ans;
    int m = l+(r-l)/2;
    if(tree[rt<<1] >= num)
        ans = query(num, lson);
    else
        ans = query(num, rson);
    pushUp(rt); //更新
    return ans;
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%d %d %d", &h, &w, &n)){
        h = min(h, n);
        build(1, h, 1);
        for(int i = 0; i < n; i++){
            int a;
            scanf("%d", &a);
            if(tree[1] < a) cout << "-1" << endl;
            else{
                cout << query(a, 1, h, 1) << endl;
            }
        }
    }
    return 0;
}