HDU2795 Billboard

十月 16, 2020 3199

题意简述

有一块高 h 宽 w 的广告牌，现在有一些高 1 宽 k 的广告，需要你依次往上贴，要求尽量往上的同时尽量靠左。对于每一个广告，输出它在哪一行，如果没地方贴就输出无解。

解题思路

一看单点修改区间查询这不就线段树吗。

考虑对高建立线段树，每一个节点储存对应区间最大的行剩余空间 segt::left。

对于每一个广告，首先判断根节点 segt[1].left 是否大于等于 k，不大于直接输出无解。
否则考虑在线段树上二分。

假设当前递归到了一个节点，我们先看它的左子树，如果 segt[lson].left 大于等于 k，就说明左子树有解，往左子树递归查答案；否则往右子树递归。一直到叶子节点，返回下标。

1
2
3
4
5
int Query(int p, int k) {
    if (segt[p].l == segt[p].r) return segt[p].down;
    if (segt[lson].left >= k) return Query(lson, k);
    else return Query(rson, k);
}

代码实现

还是比较简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 200000 + 10;

struct Node {
    int l, r, ls, rs, left, down;
    Node(int _l = 0, int _r = 0) {
        l = _l; r = _r; ls = rs = left = down = 0;
    }
} segt[MAXN * 4]; int cnt = 1;

#define lson (segt[p].ls)
#define rson (segt[p].rs)

void Update(int p) {
    if (segt[lson].left >= segt[rson].left) {
        segt[p].left = segt[lson].left;
        segt[p].down = segt[lson].down;
    } else {
        segt[p].left = segt[rson].left;
        segt[p].down = segt[rson].down;
    }
}

void buildTree(int p, int l, int r, int k) {
    segt[p] = Node(l, r);
    if (l == r) {
        segt[p].left = k; segt[p].down = l; return;
    }
    int mid = (l + r) >> 1;
    buildTree(lson = ++cnt, l, mid, k);
    buildTree(rson = ++cnt, mid + 1, r, k);
    Update(p);
}

void Modify(int p, int pos, int k) {
    if (segt[p].l == segt[p].r) {
        segt[p].left -= k;
        return;
    }
    int mid = (segt[p].l + segt[p].r) >> 1;
    if (pos <= mid) Modify(lson, pos, k);
    else Modify(rson, pos, k);
    Update(p);
}

// 在 [1, n] 中查找第一个 left >= k 的位置
int Query(int p, int k) {
    if (segt[p].l == segt[p].r) return segt[p].down;
    if (segt[lson].left >= k) return Query(lson, k);
    else return Query(rson, k);
}

int main() {
    int h, w, n;
    while (scanf("%d %d %d", &h, &w, &n) != EOF) {
        // h = read(); w = read(); n = read();
        cnt = 1; memset(segt, 0, sizeof segt);
        int mxn = h; if (h > n) mxn = n;
        buildTree(1, 1, mxn, w);
        for (int i = 1; i <= n; ++i) {
            // int w = read();
            int w; scanf("%d", &w);
            if (w > segt[1].left) {
                printf("-1\n"); continue;
            }
            int dwn = Query(1, w);
            printf("%d\n", dwn); Modify(1, dwn, w);
        }
    }
    return 0;
}