C++ 实现探测器最近管道口路程计算

好的，这是一个非常经典的 **“最近邻点”** 问题。我们来一步步分析并给出高效的C++实现。 ## 🎯 问题分析 我们有： - **n** 个管道口，位置已知（无序）。 - **m** 个探测器，位置已知。 - 每个探测器会前往**离它最近的**一个管道口。 - 计算所有探测器走过的总路程。 ### 💡 核心思路 1. **排序管道口位置**：便于快速查找最近点。 2. **对每个探测器**，在其左右两侧找到最近的管道口。 3. **比较左右距离**，取较小值。 4. **累加所有距离**。 由于 `n` 最大可达 100,000，`m` 最大 1000，我们采用 `O(m log n)` 的二分查找策略，足够高效。 --- ## 🚀 高效实现（C++） ```cpp #include <iostream> #include <algorithm> #include <vector> #include <climits> // 用于 INT_MAX using namespace std; int main() { // 1. 读取输入 int n, m; cin >> n >> m; vector<int> pipes(n); for (int i = 0; i < n; ++i) { cin >> pipes[i]; } vector<int> probes(m); for (int i = 0; i < m; ++i) { cin >> probes[i]; } // 2. 管道口排序（升序） sort(pipes.begin(), pipes.end()); // 3. 计算总路程 long long totalDistance = 0; // 用 long long 防止溢出 for (int i = 0; i < m; ++i) { int pos = probes[i]; // 使用 lower_bound 找到第一个 >= pos 的管道口位置 // lower_bound 返回迭代器 auto it = lower_bound(pipes.begin(), pipes.end(), pos); // 初始化左右距离为最大值 int leftDist = INT_MAX; int rightDist = INT_MAX; // 右侧有管道口 if (it != pipes.end()) { rightDist = *it - pos; } // 左侧有管道口（it 指向第一个 >= pos 的元素，其前一个就是 < pos 的最大元素） if (it != pipes.begin()) { leftDist = pos - *(it - 1); } // 取较近的距离 totalDistance += min(leftDist, rightDist); } // 4. 输出结果 cout << totalDistance << endl; return 0; } ``` --- ## 📖 关键点详解 ### 🔍 1. `lower_bound` 的作用 - `lower_bound(begin, end, value)` 返回**第一个大于等于** `value` 的元素的迭代器。 - **时间复杂度**：O(log n)，因为底层是二分查找。 - 如果所有元素都小于 `value`，则返回 `end()`。 ### 🔍 2. 左右距离计算 - **右侧距离**：`*it - pos` （前提是 `it` 存在） - **左侧距离**：`pos - *(it - 1)` （前提是 `it != begin()`，即存在小于 `pos` 的元素） ### ⚠️ 3. 使用 `long long` - 最坏情况：每个探测器距离最大 `100000`，`m` 最大 `1000`，总和最大 `100,000,000`，看似 `int` 够用。 - 但为了**稳健性和可扩展性**，建议使用 `long long` 避免未来数值范围修改后溢出。 --- ## ✅ 输入输出验证 ### 样例 1 ``` 输入： 5 3 9 3 23 15 29 11 18 27 排序后管道口：3 9 15 23 29 探测器： - 11：左边 9（距离2），右边 15（距离4） → 取2 - 18：左边 15（距离3），右边 23（距离5） → 取3 - 27：左边 23（距离4），右边 29（距离2） → 取2 总和：2 + 3 + 2 = 7 ✅ ``` ### 样例 2 ``` 输入： 4 3 5 11 19 7 6 7 17 排序后管道口：5 7 11 19 探测器： - 6：左边 5（距离1），右边 7（距离1） → 取1 - 7：正好等于管道口 7 → 距离0 - 17：左边 11（距离6），右边 19（距离2） → 取2 总和：1 + 0 + 2 = 3 ✅ ``` --- ## 💡 开发建议 1. **数据预处理的重要性**：排序是这类“最近邻”问题的关键前置步骤。 2. **二分查找与暴力法的选择**：本题 `m` 不大，但 `n` 很大，二分查找可以将 `O(n*m)` 降为 `O(m log n)`。 3. **边界条件处理**：题目保证“探测器左右各至少有一个管道口”，但在通用代码中仍要处理边界情况，使代码更健壮。 4. **使用 `const` 和引用**：避免不必要的拷贝，优化性能。 --- ## 🧠 进阶思考 - 如果 `m` 也很大（例如 10^5），是否可以换用**双指针**方法？可以，先将探测器和管道口都排序，然后左右滑动，达到 `O(n + m)` 的时间复杂度。 - 如果管道口可以多次使用，答案不变；如果每个管道口只能被一个探测器占用，则变成“分配问题”，解法不同。 --- ######[AI写代码神器 | 1296点数解答 | 2026-05-29 19:51:41]