题目描述 在一条笔直的马路上有 n 个塔台，它们被依次标号为 1,2,⋯,n，分别处于距离马路 起点 a1,a2,⋯,an（a1<a2<⋯<an）的位置。 每个塔台初始时有一个通讯半径 b1,b2,⋯,bn，这代表，对于 i 号塔台，其可以与 [ai−bi,ai+bi] 范围内的塔台通讯。 需要特别注意，对于两个塔台 A、B，当且仅当 A 塔台的位置处在 B 塔台的通讯范围 内，B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合，即可通 讯」。 现在你可以对这些塔台进行超频。具体的，你可以指定一个电压 k，之后所有塔台都 会被加上 k 的电压，通讯半径都会增大 k。这里的 k 仅可为非负整数。 现在要求你通过超频，使信号可以从 1 号塔台依次通过 2,3,⋯ 号塔台传输到 n 号 塔台，但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电 压。 请你计算出，为了达到以上目的，塔台超频需要的最小电压是多少。 输入格式 输入共 n+1 行。 第一行为一个整数 n，代表塔台的数量。 接下来 n 行，每行两个整数 ai,bi，分别代表各个

```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)$，主要用于存储每个塔台的位置和初始通讯半径。 [2025-11-26 20:30:18 | AI问答 | 720点数解答]