C++实现计算探测器走过路程总和的代码及分析

### 🌟问题分析 本题的目标是计算所有探测器走过的路程总和。对于每个探测器，需要找到离它最近的管道口，然后计算探测器到该管道口的距离，最后将所有探测器走过的路程相加。 ### 💻代码实现 ```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n, m; // 读取管道口的个数 n 和探测器的个数 m cin >> n >> m; vector<int> a(n); // 读取每个管道口到起点的距离 for (int i = 0; i < n; i++) { cin >> a[i]; } // 对管道口的距离进行排序 sort(a.begin(), a.end()); int sum = 0; for (int i = 0; i < m; i++) { int k; // 读取每个探测器落地时到起点的距离 cin >> k; int l = 0, r = n - 1; int mid; int ans = 0; // 二分查找离探测器最近的管道口 while (l < r) { mid = (l + r) / 2; if (a[mid] < k) { l = mid + 1; } else { r = mid; } } // 计算探测器到最近管道口的距离 ans = min(abs(k - a[l]), abs(k - (l > 0 ? a[l - 1] : a[l]))); // 将该探测器走过的路程累加到总和中 sum += ans; } // 输出所有探测器走过的路程总和 cout << sum << endl; return 0; } ``` ### 📝代码解释 1. **变量说明**： - `n`：管道口的个数。 - `m`：探测器的个数。 - `a`：存储每个管道口到起点的距离的数组。 - `k`：每个探测器落地时到起点的距离。 - `l` 和 `r`：二分查找的左右边界。 - `mid`：二分查找的中间位置。 - `ans`：当前探测器到最近管道口的距离。 - `sum`：所有探测器走过的路程总和。 2. **二分查找**： - 对管道口的距离数组 `a` 进行排序。 - 对于每个探测器的位置 `k`，使用二分查找找到离它最近的管道口。 - 计算探测器到最近管道口的距离，并累加到 `sum` 中。 ### ⚙️复杂度分析 - **时间复杂度**：排序的时间复杂度为 $O(n log n)$，二分查找的时间复杂度为 $O(m log n)$，因此总的时间复杂度为 $O(n log n + m log n)$。 - **空间复杂度**：主要使用了一个长度为 `n` 的数组来存储管道口的距离，因此空间复杂度为 $O(n)$。 ### 🚀开发建议 - **边界条件处理**：在二分查找时，需要注意边界条件，确保不会越界。 - **代码可读性**：可以添加适当的注释，提高代码的可读性。 - **错误处理**：可以添加输入验证，确保输入的合法性。 ######[AI写代码神器 | 800点数解答 | 2026-04-11 20:08:48]