题解：P12633 [UOI 2020] Skyscraper

Lonely_Peak · 2025-05-28 16:21:22 · 题解

题目大意

有 n 座大楼需要建造，每座大楼都有两个属性：高度与美观度。这些大楼都建在同一条直线上。我们需要找到一种排序的方法，使得从左往右看这些大楼，所有可见楼层的总美观度最大。

解题思路

这道题可以通过贪心法来做，我们只需要找到一种排序方法，使得总美观度最大，然后再计算总美观度即可。

为了最大化总美观度，我最开始想的是尽量让高的摩天大楼在后面，这样前面的摩天大楼较矮，后面的摩天大楼较高，可以让更多的楼层被看见。但是有个问题，要是出现像题中举出的例子中的摩天大楼，被遮挡的部分美观度较小，损失小于回报。

那么应该怎么办呢？经过思考，我猜测最优策略可能是将摩天大楼按照美观度降序排列，如果美观度相同则按高度升序排列。因为这样可以使价值大的先被看见，使得总美观度尽量大。

来通过输入输出样例验证一下：

对于样例输入#1：

排序后的大楼为 (2,4)，(4,3)，(1,2)，(3,1)。
那么总美观度就是 4\times 2 + 2\times 3 = 14。正确。

对于样例输入#2：

排序后的大楼为 (1,8)，(2,6)，(8,5)，(9,4)，(10,3)，(3,2)。
那么总美观度就是 8\times 1 + 6\times 1 + 5\times 6+4\times 1+3\times1 = 51。正确。

那么，我们的程序应该完成以下内容：

将摩天大楼按照美观度降序排列。如果美观度相同，则按照高度升序排列。
遍历排序后的摩天大楼，对于每个摩天大楼：如果它的高度 h 大于已看到的最大高度 maxh，则它的可见楼层数是 h - maxh，美观度为 w \times (h - maxh)（w 为当前大楼的美观度）。更新 maxh 为当前摩天大楼的高度 h。

参考代码

#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
using namespace std;
const int W = 1e5 + 5;
struct building {
    int high, vis;
} a[W];
int n, ans;
bool cmp(building x, building y) {
    if (x.vis == y.vis) return x.high < y.high;
    else return x.vis > y.vis;
} //首先按照 vis 降序排列。如果 vis 相同，则按照 high 升序排列。
signed main() {
    fast_running;
    cin >> n;
    for (Rint i = 1; i <= n; i++) cin >> a[i].high;
    for (Rint i = 1; i <= n; i++) cin >> a[i].vis;
    sort(a + 1, a + n + 1, cmp);  //使用 cmp 函数对摩天大楼进行排序。 
    int maxn = 0;
    for (Rint i = 1; i <= n; i++) {  //计算总美观度
        if (a[i].high > maxn) {
            ans += a[i].vis * (a[i].high - maxn);
            maxn = a[i].high;
        }
    }
    cout << ans << '\n';
    return 0;
}

~ 完结撒花 ~