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

为了达到信号从1号塔台传输到n号塔台的目的，我们可以采用二分查找的方法来确定最小电压。具体的步骤如下： 1. 初始化电压的最小值为0，最大值为a_n - a_1，其中a_n和a_1分别表示最后一个和第一个塔台的位置。 2. 在每次二分查找中，假设当前的电压为mid，将所有塔台的通讯半径都增加mid，然后检查是否存在从1号塔台到n号塔台的连通路径。 3. 为了检查连通性，我们可以使用并查集数据结构。首先将1号塔台与其通讯范围内的塔台进行合并，然后再依次将其他塔台与其通讯范围内的塔台进行合并。最后检查1号塔台和n号塔台是否在同一个集合中，如果是，则表示存在连通路径。 4. 根据检查结果，如果存在连通路径，则将电压最大值更新为当前电压mid，然后继续在更小的电压范围内进行二分查找。如果不存在连通路径，则将电压最小值更新为当前电压mid + 1，然后继续在更大的电压范围内进行二分查找。 5. 重复步骤2到步骤4，直到电压最小值等于电压最大值时结束二分查找。此时的电压最小值即为所求的最小电压。 下面是一个示例的C++代码实现： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100005; int n; int a[MAX_N], b[MAX_N]; // 并查集数据结构 int parent[MAX_N]; int find(int x) { if (parent[x] == x) { return x; } return parent[x] = find(parent[x]); } void unite(int x, int y) { int px = find(x); int py = find(y); if (px != py) { parent[py] = px; } } bool connected() { return find(1) == find(n); } bool check(int voltage) { // 初始化并查集 for (int i = 1; i <= n; i++) { parent[i] = i; } // 合并塔台 for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (abs(a[i] - a[j]) <= voltage && abs(b[i] - b[j]) <= voltage) { unite(i, j); } } } return connected(); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { cin >> b[i]; } int minVoltage = 0; int maxVoltage = a[n] - a[1]; while (minVoltage < maxVoltage) { int mid = (minVoltage + maxVoltage) / 2; if (check(mid)) { maxVoltage = mid; } else { minVoltage = mid + 1; } } cout << minVoltage << endl; return 0; } ``` 注意，以上代码假设输入满足题目描述中的条件，即塔台位置按升序排列。在实际使用中，应根据实际情况进行输入验证和错误处理。