HDU 2795 Billboard（宣传栏贴公告，线段树应用）

ACM

题目地址：HDU 2795 Billboard

题意： 

要在h*w宣传栏上贴公告，每条公告的高度都是为1的，并且每条公告都要尽量贴最上面最靠左边的，给你一系列的公告的长度，问它们能不能贴上。

分析： 

不是非常好想，只是想到了就非常好写了。 

仅仅要把宣传栏倒过来就好办了，这时候就是变成有h条位置能够填公告，填放公告时就能够尽量找最左边的合适的位置来放了。 

能够用线段树实现，查找的复杂度是O(logn)，须要注意的坑点是h的范围很大，假设真的那么大线段树是开不下去的，可是n的范围才20w，而即使全部公告都要占一栏也不会超过n，所以线段树开min(h, n)即可了。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  Blog:        http://blog.csdn.net/hcbbt

*  File:        2795.cpp

*  Create Date: 2014-08-05 16:12:47

*  Descripton:  segment tree

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

#define repf(i,a,b) for(int i=(a);i<=(b);i++)

#define lson(x) ((x) << 1)

#define rson(x) ((x) << 1 | 1)

typedef long long ll;

const int N = 200010;

const int ROOT = 1;

int h, w, n, t;

// below is sement point updated version

struct seg {

    ll w;

};

struct segment_tree {

    seg node[N << 2];

    void update(int pos) {

        node[pos].w = max(node[lson(pos)].w, node[rson(pos)].w);

    }

    void build(int l, int r, int pos) {

        if (l == r) {

            node[pos].w = w;

            return;

        }

        int m = (l + r) >> 1;

        build(l, m, lson(pos));

        build(m + 1, r, rson(pos));

        update(pos);

    }

    int queryandmodify(int l, int r, int pos, ll y) {

        if (y > node[pos].w) {

            return -1;

        }

        if (l == r) {

            node[pos].w -= y;

            return l;

        }

        int m = (l + r) >> 1;

        int res;

        if (y <= node[lson(pos)].w)

            res = queryandmodify(l, m, lson(pos), y);

        else

            res = queryandmodify(m + 1, r, rson(pos), y);

        update(pos);

        return res;

    }

} sgm;

int main() {

    while (~scanf("%d%d%d", &h, &w, &n)) {

        h = min(h, n);

        sgm.build(1, h, ROOT);

        repf (i, 1, n) {

            scanf("%d", &t);

            printf("%d\n", sgm.queryandmodify(1, h, ROOT, t));

        }

    }

    return 0;

}