塔台超频 - 最小超频电压算法详解

塔台超频 - 最小超频电压算法详解\n\n题目描述\n\n在一条笔直的马路上有 $n$ 个塔台，它们被依次标号为 $1, 2, \cdots, n$，分别处于距离马路起点 $a _ 1, a _ 2, \cdots, a _ n$（$a _ 1 < a _ 2 < \cdots < a _ n$）的位置。\n\n每个塔台初始时有一个通讯半径 $b _ 1, b _ 2, \cdots, b _ n$，这代表，对于 $i$ 号塔台，其可以与 $[a _ i - b _ i, a _ i + b _ i]$ 范围内的塔台通讯。\n\n需要特别注意，对于两个塔台 A、B，当且仅当 A 塔台的位置处在 B 塔台的通讯范围内，B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合，即可通讯」。\n\n现在你可以对这些塔台进行超频。具体的，你可以指定一个电压 $k$，之后所有塔台都会被加上 $k$ 的电压，通讯半径都会增大 $k$。这里的 $k$ 仅可为非负整数。\n\n现在要求你通过超频，使信号可以从 $1$ 号塔台依次通过 $2, 3, \cdots$ 号塔台传输到 $n$ 号塔台，但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电压。\n\n请你计算出，为了达到以上目的，塔台超频需要的最小电压是多少。\n\n输入格式\n\n输入共 $n + 1$ 行。\n\n第一行为一个整数 $n$，代表塔台的数量。\n接下来 $n$ 行，每行两个整数 $a _ i, b _ i$，分别代表各个塔台的位置和初始通讯半径。\n\n输出格式\n\n输出共一行一个整数，代表为了达到目的，塔台超频需要的最小电压。\n\n样例 #1\n\n样例输入 #1\n\n\n5\n0 4\n2 2\n3 1\n12 8\n19 2\n\n\n样例输出 #1\n\n\n8\n\n\n提示\n\n数据规模与约定\n\n对于 $100%$ 的数据，保证 $2 \leq n \leq 5 \times 10 ^ 5$，$0 \leq a _ i, b _ i \leq 10 ^ 9$。\n\n| 测试点编号 | 特殊限制 |\n| :----------: | :----------: |\n| $1 \sim 2$ | $n \leq 10$，$a _ i, b _ i \leq 200$ |\n| $3$ | $a _ i = i$ |\n| $4 \sim 5$ | $b _ i = 0$ |\n| $6$ | 所有 $b _ i$ 相同 |\n| $7 \sim 10$ | 无特殊限制 |\n\n解题思路\n\n我们可以将问题转化为求最小的电压 $k$，使得对于任意的 $i$，第 $i$ 个塔台的位置 $a_i$ 在 $(a_i - b_i, a_i + b_i + k]$ 这个范围内。也就是说，对于任意的 $i$，第 $i$ 个塔台的位置 $a_i$ 要在前面的塔台的通讯范围内。\n\n我们可以将塔台按照位置从小到大排序，然后依次遍历每个塔台。对于第 $i$ 个塔台，我们需要找到前面的塔台中通讯范围覆盖位置 $a_i$ 最远的塔台，记为 $j$。然后我们可以得到第 $i$ 个塔台的最小通讯范围为 $(a_j - b_j, a_j + b_j + k]$，也就是 $a_i$ 要在 $(a_j - b_j, a_j + b_j + k]$ 这个范围内。\n\n我们可以用一个数组 $dp$ 来记录每个位置的最小通讯范围。对于第 $i$ 个塔台，我们可以通过遍历前面的塔台，找到最远的塔台 $j$，然后通过 $dp[j]$ 来计算 $dp[i]$ 的值。具体的计算方法如下：\n\n1. 初始化 $dp[0] = b_0 + k$，其中 $b_0$ 是第一个塔台的初始通讯半径。\n2. 对于 $i$ 从 $1$ 到 $n-1$，执行以下步骤：\n - 找到前面的塔台中通讯范围覆盖位置 $a_i$ 最远的塔台 $j$。\n - 计算 $dp[i]$ 的值：$dp[i] = \max(dp[i], a_j + b_j + k)$。\n3. 最终的答案为 $dp[n-1]$。\n\n这样我们就可以通过动态规划的方法求出最小的电压 $k$。\n\n复杂度分析\n\n排序的时间复杂度为 $O(n \log n)$，动态规划的时间复杂度为 $O(n)$。因此总的时间复杂度为 $O(n \log n)$。空间复杂度为 $O(n)$。\n\nC++代码\n\ncpp\n#include <iostream>\n#include <algorithm>\nusing namespace std;\n\nconst int MAXN = 5e5 + 5;\n\nstruct Tower {\n int pos, radius; \n};\n\nbool cmp(const Tower &a, const Tower &b) {\n return a.pos < b.pos; \n}\n\nint main() {\n int n; \n cin >> n; \n Tower towers[MAXN]; \n for (int i = 0; i < n; i++) {\n cin >> towers[i].pos >> towers[i].radius; \n }\n sort(towers, towers + n, cmp); \n int dp[MAXN]; \n dp[0] = towers[0].radius; \n for (int i = 1; i < n; i++) {\n int j = i - 1; \n while (j >= 0 && towers[i].pos > towers[j].pos + towers[j].radius) {\n j--; \n }\n dp[i] = max(dp[i], towers[j].pos + towers[j].radius); \n }\n cout << dp[n - 1] - towers[n - 1].radius << endl; \n return 0; \n}\n