算法|题解

计蒜客 – 公告板

凝神长老 · 3月5日 · 2020年 · · 764次已读

计蒜客 – 公告板

蒜厂有一个 $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;
}

更多线段树相关的题目

订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论