巧用二分查找：求解塔台超频最小电压实现信号依次传输

```cpp #include <iostream> #include <vector> using namespace std; // 检查在给定电压 k 下，信号是否能从 1 号塔台依次传输到 n 号塔台 bool canReach(const vector<int>& a, const vector<int>& b, int k) { int currentPos = a[0]; int currentRange = a[0] + b[0] + k; for (int i = 1; i < a.size(); ++i) { if (a[i] <= currentRange) { currentPos = a[i]; currentRange = a[i] + b[i] + k; } else { return false; } } return true; } // 二分查找最小电压 int findMinVoltage(const vector<int>& a, const vector<int>& b) { int left = 0, right = 1e9; int result = right; while (left <= right) { int mid = left + (right - left) / 2; if (canReach(a, b, mid)) { result = mid; right = mid - 1; } else { left = mid + 1; } } return result; } int main() { int n; cin >> n; vector<int> a(n); vector<int> b(n); for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; } int minVoltage = findMinVoltage(a, b); cout << minVoltage << endl; return 0; } ``` 代码解释： 1. `canReach` 函数：该函数用于检查在给定电压 `k` 下，信号是否能从 1 号塔台依次传输到 `n` 号塔台。它遍历每个塔台，如果当前塔台的位置在当前可到达的范围内，则更新当前位置和可到达范围；否则，返回 `false`。 2. `findMinVoltage` 函数：使用二分查找来找到最小的满足条件的电压。左端点 `left` 初始化为 0，右端点 `right` 初始化为 `1e9`。在二分查找过程中，取中间值 `mid`，调用 `canReach` 函数检查是否能到达。如果可以到达，则更新结果并缩小右边界；否则，扩大左边界。 3. `main` 函数：读取输入的塔台数量 `n` 和每个塔台的位置和初始通讯半径，调用 `findMinVoltage` 函数计算最小电压，并输出结果。 复杂度分析： - 时间复杂度：$O(n \log m)$，其中 $n$ 是塔台的数量，$m$ 是最大可能的电压值。二分查找的时间复杂度是 $O(\log m)$，每次检查的时间复杂度是 $O(n)$。 - 空间复杂度：$O(n)$，主要用于存储每个塔台的位置和初始通讯半径。 ######[AI问答 | 720点数解答 | 2025-11-26 20:30:18]