[CRCI2007-2008] PLATFORME 平板

题意

给出若干水平平板，每块平板由高度 h 和水平区间 [l, r] 决定。

每块平板左右两端都需要有支柱或者落在别的平板上。

要求计算支撑所有平板所需支柱总长度。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解。
// 对每个平板的左右支柱，分别枚举所有更低的平板，找离它最近的支撑高度。

const int MAXN = 105;

struct Platform {
    int h, l, r;
};

int n;
Platform a[MAXN];

bool cmp_platform(const Platform &A, const Platform &B) {
    return A.h < B.h;
}

int find_support_height(int idx, int cell) {
    int best = 0;
    for (int j = 1; j < idx; j++) {
        if (a[j].l <= cell && cell + 1 <= a[j].r) {
            best = max(best, a[j].h);
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].h >> a[i].l >> a[i].r;
    }

    sort(a + 1, a + n + 1, cmp_platform);

    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        int left_support = find_support_height(i, a[i].l);
        int right_support = find_support_height(i, a[i].r - 1);
        answer += a[i].h - left_support;
        answer += a[i].h - right_support;
    }

    cout << answer << '\n';
    return 0;
}

brute.cpp 对每块平板的左右支柱分别枚举所有更低平板，找出下方最近的支撑高度。

这个思路很直观，也足够做小数据对拍。

更进一步的观察是：支柱只会落在两个单位小格上：

左支柱看 [l, l+1]
右支柱看 [r-1, r]

如果我们按高度从低到高处理平板，并维护每个单位小格当前最高平板高度 top_height[x]，那么：

左支柱长度就是 h - top_height[l]
右支柱长度就是 h - top_height[r-1]

计算完一块平板后，再把它覆盖的所有单位小格高度更新成 h。

这样后面更高的平板，就能直接在这些小格里找到自己最近的支撑面。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXX = 10005;

struct Platform {
    int h, l, r;
};

int n;
Platform a[MAXN];
int top_height[MAXX]; // top_height[x] 表示单位小格 [x, x+1] 当前最高的已建平板高度

bool cmp_platform(const Platform &A, const Platform &B) {
    return A.h < B.h;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].h >> a[i].l >> a[i].r;
    }

    sort(a + 1, a + n + 1, cmp_platform);

    long long answer = 0;

    for (int i = 1; i <= n; i++) {
        int h = a[i].h;
        int l = a[i].l;
        int r = a[i].r;

        // 左右支柱分别立在 [l,l+1] 和 [r-1,r] 这两个单位小格上方。
        answer += h - top_height[l];
        answer += h - top_height[r - 1];

        // 当前平板搭好后，它会成为自己覆盖范围内最高的平板。
        for (int x = l; x <= r - 1; x++) {
            top_height[x] = h;
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

排序： $O(N log N)$
更新覆盖小格：在本题范围内足够小

空间复杂度：

$O(X)$

其中 X 是横坐标范围。

总结

这题的关键不是去盯着“支柱”本身，而是改成想：

这根支柱脚下那个单位小格
当前最高的支撑面是谁

一旦完成这个转化，整题就会非常顺。

[CRCI2007-2008] PLATFORME 平板

目录

题意

思路

代码

复杂度

总结