题解：P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2)

· · 题解

概况

本题可归结为二维点的离线统计，结合二分法解决最小曼哈顿距离问题。

重要思路：曼哈顿距离转化为切比雪夫距离，可参考 OI-Wiki：

核心思路（简短版）

  1. 曼哈顿距离转化为切比雪夫距离

    给定旧点 (x, y)，构造新点：

    (X, Y) = (x + y, x - y)

    转换后，原本的曼哈顿距离问题可以通过切比雪夫距离处理。

  2. 二分答案 + 离线数点

    • 对第 k 条最便宜道路的花费，进行二分判断。
    • 使用离线统计方法计算，某个候选距离是否至少有 k 条道路满足条件。
    • 当满足条件时，即可确定当前距离为答案的一部分。

Code

（略）

AC Link（虽然我的作答思路和题解思路可能不太一致）

::::info[AI 提示]{open}

本题解由 ChatGPT-5 润色，其中 AC 代码编写与题解大意由笔者把持。

::::