UOI 2020 Stage 4 Day1 - 摩天大楼 题解

题目概述

科扎克·武斯需要建造 n 座摩天大楼，这些大楼必须位于同一条直线上，且他的大楼在最左边。第 i 座大楼距离他的大楼 i 公里，高度为 a_i 层，每层美丽值为 b_i。

关键规则：一座大楼的第 i 层只有在它与科扎克大楼之间没有其他大楼也拥有第 i 层时，才会被看到。

目标：通过合理安排大楼的建造顺序，使得从科扎克大楼能看到的所有楼层的美丽值之和最大化。

问题分析

核心观察

1. 可见性条件：对于任意高度 h，只有距离最近的高度 ≥ h 的大楼的第 h 层是可见的
2. 单调栈思想：这实际上是一个在高度维度上的"最近更大值"问题
3. 贪心策略：我们应该优先安排美丽值高的大楼在关键位置

数学模型

将问题重新表述：

• 我们需要为每个高度 h (1 ≤ h ≤ max_a) 分配一个大楼
• 对于高度 h，我们选择美丽值最大的可用大楼
• 但约束是：如果选择了高度为 a 的大楼，那么它贡献的可见楼层是从某个起始高度到 a

解题思路

贪心算法

1. 按美丽值排序：将大楼按美丽值 b 降序排序，美丽值相同时按高度 a 降序排序
2. 维护当前最大高度：记录已经覆盖的最大高度 max_h
3. 遍历处理：对于每个大楼，如果它的高度大于当前最大高度，则：
   • 计算新增的可见楼层数：(a_i - max_h)
   • 这些新增楼层的美丽值都是 b_i
   • 更新总美丽值和最大高度

算法正确性证明

为什么这样贪心是正确的？

• 美丽值优先：由于 b_i 是每层的美丽值，我们希望尽可能多的高层使用大的 b_i
• 高度利用：当处理美丽值大的大楼时，我们希望它贡献尽可能多的新楼层
• 无后效性：后面的选择不会影响前面已经确定的可见楼层

算法实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

struct Building {
    ll a, b;
};

// 排序规则：按b降序，若b相同则按a降序
bool cmp(const Building& x, const Building& y) {
    if (x.b != y.b) {
        return x.b > y.b;
    }
    return x.a > y.a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<Building> buildings(n);
    for (int i = 0; i < n; ++i) {
        cin >> buildings[i].a;
    }
    for (int i = 0; i < n; ++i) {
        cin >> buildings[i].b;
    }
    
    sort(buildings.begin(), buildings.end(), cmp);
    
    ll max_h = 0;
    ll total = 0;
    
    for (auto& bld : buildings) {
        if (bld.a > max_h) {
            total += (bld.a - max_h) * bld.b;
            max_h = bld.a;
        }
    }
    
    cout << total << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，用于存储大楼信息

样例分析

样例1

输入：
4
2 1 3 4
4 2 1 3

处理过程：
排序后：(a=2,b=4), (a=4,b=3), (a=1,b=2), (a=3,b=1)
- 处理(2,4)：新增高度1-2，贡献2×4=8
- 处理(4,3)：新增高度3-4，贡献2×3=6  
- 其他大楼不增加新高度
总美丽值：8+6=14

样例2

输入：
6
1 10 3 9 8 2
8 3 2 4 5 6

处理过程：
排序后按b降序处理，计算新增高度贡献
最终得到总美丽值51

总结

这道题的关键在于将复杂的可见性条件转化为简单的贪心选择问题。通过按美丽值排序并维护当前达到的最大高度，我们可以高效地计算出最大总美丽值。

核心技巧：

1. 识别出这是一个"按美丽值分配高度区间"的问题
2. 使用排序贪心策略
3. 维护当前覆盖的高度范围

这种贪心思路在很多区间分配问题中都有应用，是竞赛中的经典技巧。