「BalticOI 2012 Day2」城市烟花 题解

问题分析

这个问题要求在城市主干道（水平街道 $0$）与某条竖直街道的交点处燃放烟花，使得所有市民为观赏烟花移动的总距离最小，同时满足安全距离 $S$ 的约束。

关键约束条件

• 烟花燃放点固定在水平街道 $0$ 上，坐标为 $(0, V)$，其中 $V$ 是待选择的竖直街道编号
• 市民只能在水平街道 $0$ 或竖直街道 $V$ 上观赏烟花
• 观赏点与燃放点的直线距离必须至少为 $S$
• 目标是最小化所有市民从家到观赏点的曼哈顿距离之和

算法思路

核心观察

对于每个市民 $(H_i, V_i)$，其最优移动策略取决于烟花燃放位置 $V$ 的取值。随着 $V$ 的变化，市民的最佳观赏位置和所需移动距离会发生变化。

扫描线方法

算法采用扫描线技术，按竖直坐标 $V$ 从小到大处理所有关键点：

1. 关键点识别：确定所有可能引起市民状态变化的 $V$ 坐标值

   • $x - y$：从一种移动策略切换到另一种
   • $x$：状态转换点
   • $x + y$：状态转换点
   • $x - S$：安全距离边界
   • $x + S$：安全距离边界

2. 离散化处理：将所有关键点坐标离散化，减少问题规模

3. 状态维护：为每个市民预计算在所有可能状态下的移动距离

4. 增量更新：在扫描过程中，当遇到关键点时更新受影响市民的状态，并维护当前总距离

算法实现细节

状态定义

每个市民有7种可能的状态，对应不同的移动策略：

• 状态0：在竖直街道上观赏，满足安全距离约束
• 状态1：在竖直街道上观赏，位于燃放点左侧
• 状态2：在竖直街道上观赏，位于燃放点右侧
• 状态3-6：在水平街道上观赏，考虑不同的安全距离情况

数据结构

• 使用多个向量数组 L1 到 L5 分别存储不同类型关键点对应的市民索引
• 维护 cur[i] 数组记录每个市民当前的状态
• 维护 f[i][0..6] 数组预计算每个市民在各状态下的移动距离

扫描过程

从左到右扫描所有离散化后的关键点：

• 在每个关键点处，更新所有受影响的市民状态
• 计算当前 $V$ 坐标下的总移动距离
• 跟踪所有位置中的最小值

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自排序和离散化
• 空间复杂度：$O(N)$，存储市民信息和关键点映射
• 扫描过程：每个市民最多被处理常数次

算法标签

主要算法

扫描线算法 - 通过按坐标顺序处理事件来解决问题

离散化技术 - 将连续坐标映射到离散索引以降低复杂度

优化方法

增量计算 - 在状态变化时增量更新总距离而非重新计算

事件驱动 - 只在关键点处进行状态更新和计算

问题类型

几何优化问题 - 在二维网格上寻找最优位置

约束优化 - 在安全距离约束下最小化总移动距离

应用特征

大规模数据处理 - 支持 $N \leq 10^5$ 的数据规模

实数坐标处理 - 处理范围达 $-10^9$ 到 $10^9$ 的坐标值

这个解决方案通过巧妙的离散化和扫描线技术，将原本需要枚举所有可能位置的问题转化为高效的事件处理过程，体现了算法设计在解决复杂几何优化问题中的重要性。