Visits: 108

计蒜客 – 公告板

蒜厂有一个 $h\times w$ 的矩形公告板，其中 $h$ 是高度，$w$ 是宽度。

现在有若干张 $1\times W_i$ 的公告， $W_i$ 是宽度，公告只能横着放，即高度为 $1$ 的边垂直于水平面，且不能互相有重叠，每张公告都要求尽可能的放在最上面的合法的位置上。

若可以放置，输出每块可放置的位置的行号；若不存在，输出 $-1$。行号由上至下分别为 $1,2,…,h$。

输入格式

第一行三个整数 $h$，$w$，$n$ ($1 \leq h,w \leq 10^9; 1 \leq n \leq 200,000$) 。

接下来 $n$ 行，每行一个整数 $W_i$ ($1 \leq W_i\leq 10^9$) 。

3 5 5
2
4
3
3
3

输出格式

输出 $n$ 行，一行一个整数。

1
2
1
3
-1

这道题需要多花一点心思，改一改线段树的修改函数。

// 修改
// 由于本题不是给特定节点 x 进行 s[x] + v，所以不需要找到 x 是当前的左孩子还是右孩子
int modify(int p, int l, int r, int v)
{
    // 这个条件当然可以放在 if (l == r) { if (s[p] + v <= w) {} } 里面去判断，一样能得到正确的结果
    // 但是最后一组测试数据会超时，因此需要提前剪枝，如果已经放不下了，就没必要放了
    // 但是怎么知道已经放不下了，s[p] + v > w 这个条件很可能经常成立，所以一直是 return -1，而返回值大于 0 才能输出，如一直是 -1 就要一直继续往后找
    // 所以 s[p] 需要保存 min(s[p * 2], s[p * 2 + 1])，如果左右孩子最短的都已经放不下了，才是真的 -1
    // 否则，若 s[p] + v < w，就说明他的孩子中有一个可以贴，那就找到它，然后 return 一个大于 0 的值，提前剪枝
    if (s[p] + v > w) {
        return -1;
    }
    if (l == r) {
        // 叶结点则可以判断到底是不是贴的下，即，叶子节点就是递归终止的条件
        if (s[p] + v <= w) {
            // 已经贴了的长度加上海报的长度，如果小于宽度，说明贴的下
            // 由于题目要求必须贴在最上面一行，所以一旦放得下，就直接贴了，不需要再往孩子结点去找全局最优
            s[p] += v;
            // l == r，因此 l 就是当前行号
            return l;
        } else {
            // 任何情况下贴不下就返回 -1
            return -1;
        }
    }

    int mid = (l + r) / 2;
    int temp = modify(p * 2, l, mid, v);
    if (temp > 0) {
        // 如果 temp 大于 0，说明找到了贴的地方，直接返回，否则，就要继续找
    } else {
        temp = modify(p * 2 + 1, mid + 1, r, v);
    }
     s[p] = min(s[p * 2], s[p * 2 + 1]); // 这里必须留下最短的，否则会超时
    return temp;
}

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000 * 3 + 7; // 由于还要 2 倍的父节点，所以乘以 3
int s[MAX_N] = {0};
int h = 0, w = 0, n = 0;

// 修改
// 由于本题不是给特定节点 x 进行 s[x] + v，所以不需要找到 x 是当前的左孩子还是右孩子
int modify(int p, int l, int r, int v)
{
    // 这个条件当然可以放在 if (l == r) { if (s[p] + v <= w) {} } 里面去判断，一样能得到正确的结果
    // 但是最后一组测试数据会超时，因此需要提前剪枝，如果已经放不下了，就没必要放了
    // 但是怎么知道已经放不下了，s[p] + v > w 这个条件很可能经常成立，所以一直是 return -1，而返回值大于 0 才能输出，如一直是 -1 就要一直继续往后找
    // 所以 s[p] 需要保存 min(s[p * 2], s[p * 2 + 1])，如果左右孩子最短的都已经放不下了，才是真的 -1
    // 否则，若 s[p] + v < w，就说明他的孩子中有一个可以贴，那就找到它，然后 return 一个大于 0 的值，提前剪枝
    if (s[p] + v > w) {
        return -1;
    }
    if (l == r) {
        // 叶结点则可以判断到底是不是贴的下，即，叶子节点就是递归终止的条件
        if (s[p] + v <= w) {
            // 已经贴了的长度加上海报的长度，如果小于宽度，说明贴的下
            // 由于题目要求必须贴在最上面一行，所以一旦放得下，就直接贴了，不需要再往孩子结点去找全局最优
            s[p] += v;
            // l == r，因此 l 就是当前行号
            return l;
        } else {
            // 任何情况下贴不下就返回 -1
            return -1;
        }
    }

    int mid = (l + r) / 2;
    int temp = modify(p * 2, l, mid, v);
    if (temp > 0) {
        // 如果 temp 大于 0，说明找到了贴的地方，直接返回，否则，就要继续找
    } else {
        temp = modify(p * 2 + 1, mid + 1, r, v);
    }
     s[p] = min(s[p * 2], s[p * 2 + 1]); // 这里必须留下最短的，否则会超时
    return temp;
}

// 封装后的修改，以供调用
/**
 *
 * @param v 海报的宽度
 * @return 如果能贴的下，返回最上面的一行的序号，如果贴不下，返回 -1
 */
int modify(int v) {
    // 注意这里是 h 了，因为最大高度是 h
    return modify(1, 1, h, v);
}

int main() {
    scanf("%d%d%d", &h, &w, &n);
    for (int i = 1; i <= n; i++) {
        int wi;
        scanf("%d", &wi);
        printf("%d\n", modify(wi));
    }
    return 0;
}