程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2795 Billboard（宣傳欄貼公告，線段樹應用）

HDU 2795 Billboard（宣傳欄貼公告，線段樹應用）

編輯：C++入門知識

HDU 2795 Billboard（宣傳欄貼公告，線段樹應用）

ACM

題目地址：HDU 2795 Billboard

題意：
要在h*w宣傳欄上貼公告，每條公告的高度都是為1的，而且每條公告都要盡量貼最上面最靠左邊的，給你一系列的公告的長度，問它們能不能貼上。

分析：
不是很好想，不過想到了就很好寫了。
只要把宣傳欄倒過來就好辦了，這時候就是變成有h條位置可以填公告，填放公告時就可以盡量找最左邊的合適的位置來放了。
可以用線段樹實現，查找的復雜度是O(logn)，需要注意的坑點是h的范圍非常大，如果真的那麼大線段樹是開不下去的，但是n的范圍才20w，而即使所有公告都要占一欄也不會超過n，所以線段樹開min(h, n)就行了。

代碼：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2795.cpp
*  Create Date: 2014-08-05 16:12:47
*  Descripton:  segment tree 
*/

#include 
#include 
#include 
#include 
#include 
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;
}