「建造桥梁」题解

问题分析

我们需要在河上建造最多 $K$ 座桥（$K \leq 2$），使得所有居民从家到办公室的总距离最小。

关键观察：

1. 如果居民的家和办公室在同一侧（$P_i = Q_i$），那么他的通行与桥无关，直接沿河岸走，距离为 $|S_i - T_i|$。
2. 如果居民的家和办公室在不同侧（$P_i \ne Q_i$），他需要过河。过河有两种方式：
   • 通过桥过河：先沿河岸走到桥的位置，过桥，再沿对岸走到办公室
   • 直接坐船：直接垂直过河，但题目似乎暗示必须开车，所以只能通过桥

距离计算

对于跨河居民 $i$（假设家在区域 $A$ 的 $S_i$，办公室在区域 $B$ 的 $T_i$）：

• 如果通过位于位置 $x$ 的桥过河，距离为 $|S_i - x| + 1 + |T_i - x|$
• 其中 $1$ 是过桥的固定距离（河宽）

因此，这个居民对总距离的贡献为：

$$D_i = |S_i - x| + |T_i - x| + 1$$

我们要最小化所有跨河居民的 $D_i$ 之和。

$K=1$ 的情况（子任务1-2）

当只有一座桥时，问题简化为：选择桥的位置 $x$，最小化：

$$F(x) = \sum_{\text{跨河居民} i} (|S_i - x| + |T_i - x| + 1) $$

由于常数项 $\sum 1$ 是固定的，我们只需要最小化：

$$G(x) = \sum_{\text{跨河居民} i} (|S_i - x| + |T_i - x|) $$

这是一个经典的中位数问题：最小化多个点到 $x$ 的绝对距离之和时，最优的 $x$ 是所有点的中位数。

算法步骤：

1. 将所有跨河居民的 $S_i$ 和 $T_i$ 收集到一个数组中
2. 对这个数组排序，找到中位数
3. 计算以中位数为桥位置时的总距离

时间复杂度：$O(N \log N)$，用于排序。

$K=2$ 的情况（子任务3-5）

这是本题的核心难点。

关键观察

1. 桥不能相交：这意味着桥的位置必须是有序的，设两座桥的位置为 $x_1 < x_2$。
2. 居民选择桥：每个跨河居民会选择距离他更近的桥（或其中一座），因为这样总距离更小。
3. 分离点：存在一个分离点，使得左侧的居民使用左边的桥，右侧的居民使用右边的桥。

问题转化

设两座桥的位置为 $x_1 < x_2$，分离点为 $m$（$x_1 \leq m \leq x_2$）。对于跨河居民 $i$：

• 如果 $S_i, T_i$ 的中点在 $m$ 左边（或等于），使用桥 $x_1$
• 否则使用桥 $x_2$

但更准确地说：居民 $i$ 会选择使 $|S_i - x| + |T_i - x|$ 更小的桥。

动态规划思路

状态设计： 设 $dp[i][j]$ 表示考虑前 $i$ 个跨河居民（按某种顺序排序后），使用 $j$ 座桥时的最小总距离。

但直接这样设计状态不行，因为桥的位置是连续的，不是离散的。

更聪明的做法

1. 排序：将跨河居民按照 $\min(S_i, T_i)$ 和 $\max(S_i, T_i)$ 的中点排序，或者按照 $S_i + T_i$ 排序。
2. 枚举分离点：如果我们知道了哪些居民使用第一座桥，哪些使用第二座桥，那么每组的桥位置就是该组居民所有 $S_i$ 和 $T_i$ 的中位数。
3. 优化枚举：可以枚举分离点 $i$，表示前 $i$ 个居民使用第一座桥，后面的使用第二座桥。

具体算法：

1. 预处理：

   • 分离出跨河居民，计算他们的基础距离（$|S_i - T_i|$）
   • 将跨河居民按照 $S_i + T_i$ 排序（或者按照 $\frac{S_i + T_i}{2}$ 排序）

2. 计算前缀和：

   • 设排序后的跨河居民数组为 $R[1..M]$
   • 计算前缀的 $S_i$ 和 $T_i$ 数组，用于快速计算选定居民组的中位数和距离和

3. 枚举所有分离点：

   • 对于每个可能的分离点 $i$（$0 \leq i \leq M$）：
     • 前 $i$ 个居民使用第一座桥
     • 后 $M-i$ 个居民使用第二座桥
   • 对于每组，计算最优桥位置（中位数）和相应的距离和
   • 更新最小值

4. 总距离：

   • 跨河居民的总距离 = 各组距离和 + 固定部分（$M \times 1$，因为每人都要过一次桥）
   • 加上同侧居民的距离（他们直接 $|S_i - T_i|$）

时间复杂度优化

枚举所有分离点 $O(M)$，但对于每组需要快速计算：

• 中位数：可以使用两个堆（最大堆+最小堆）动态维护，但这里更简单：
• 由于我们已经排序，对于前 $i$ 个居民，他们的中位数就是第 $\lfloor i/2 \rfloor$ 个居民的 $(S+T)/2$ 值

但更精确的做法是： 对于一组居民，设他们的所有 $S$ 和 $T$ 值组成数组 $A$，排序后求中位数 $m$，总距离为 $\sum |a - m|$。

我们可以预先计算：

• 排序后的 $S_i, T_i$ 值
• 前缀和，从而在 $O(1)$ 时间内计算任意区间的距离和

实现细节

步骤1：处理输入

• 对于每个居民，如果 $P_i = Q_i$，直接加上 $|S_i - T_i|$ 到答案
• 如果 $P_i \ne Q_i$，记录为跨河居民，保存 $S_i, T_i$

步骤2：对跨河居民排序

• 按照 $S_i + T_i$ 排序

步骤3：预处理

• 创建数组 $B$，包含所有跨河居民的 $S_i$ 和 $T_i$（共 $2M$ 个点）
• 对 $B$ 排序，计算前缀和

步骤4：动态规划计算

• $left[i]$：前 $i$ 个跨河居民使用一座桥的最小距离
• $right[i]$：从第 $i$ 个到第 $M$ 个跨河居民使用一座桥的最小距离

步骤5：枚举分离点

• 对于每个 $i$，总距离 = $left[i] + right[i+1] + M$（$M$ 是过桥的固定距离）
• 取最小值

特殊情况处理

• 当 $M=0$（没有跨河居民）时，直接输出同侧居民距离和
• 当 $K=1$ 时，不能用两座桥的算法
• 注意 $K$ 是上限，可以用少于 $K$ 座桥

复杂度分析

• 排序：$O(N \log N)$
• 预处理前缀和：$O(N)$
• 计算 $left$ 和 $right$ 数组：$O(M \log M)$ 或 $O(M)$，取决于实现
• 总复杂度：$O(N \log N)$，满足 $N \leq 10^5$ 的要求

正确性证明

1. 中位数最优性：对于一组点，最小化绝对距离和的位置是中位数。
2. 分离点性质：将居民按 $S_i+T_i$ 排序后，最优分配一定是连续的段使用同一座桥。
3. 枚举完备性：我们枚举了所有可能的分离点，因此不会错过最优解。

总结

本题的核心是：

1. $K=1$ 时：简单的中位数问题
2. $K=2$ 时：通过排序和前缀和，将问题转化为枚举分离点的优化问题
3. 关键技巧：将跨河居民按 $S_i+T_i$ 排序，保证最优分配是连续的