塔台超频 - 最小电压优化算法详解 - 常规

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

问题描述： 在一条笔直的马路上有 (n) 个塔台，它们被依次标号为 (1, 2, \cdots, n)，分别处于距离马路起点 (a _ 1, a _ 2, \cdots, a _ n)（(a _ 1 < a _ 2 < \cdots < a _ n)）的位置。

每个塔台初始时有一个通讯半径 (b _ 1, b _ 2, \cdots, b _ n)，这代表，对于 (i) 号塔台，其可以与 ([a _ i - b _ i, a _ i + b _ i]) 范围内的塔台通讯。

需要特别注意，对于两个塔台 A、B，当且仅当 A 塔台的位置处在 B 塔台的通讯范围内，B 塔台才能向 A 塔台传递信号。请注意这里不是「二者的通讯范围重合，即可通讯」。

现在你可以对这些塔台进行超频。具体的，你可以指定一个电压 (k)，之后所有塔台都会被加上 (k) 的电压，通讯半径都会增大 (k)。这里的 (k) 仅可为非负整数。

现在要求你通过超频，使信号可以从 (1) 号塔台依次通过 (2, 3, \cdots) 号塔台传输到 (n) 号塔台，但是由于不合理的超频会较严重地磨损塔台，因此你想要尽可能降低超频的电压。

请你计算出，为了达到以上目的，塔台超频需要的最小电压是多少。

输入格式： 输入共 (n + 1) 行。

第一行为一个整数 (n)，代表塔台的数量。
接下来 (n) 行，每行两个整数 (a _ i, b _ i)，分别代表各个塔台的位置和初始通讯半径。

输出格式： 输出共一行一个整数，代表为了达到目的，塔台超频需要的最小电压。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 (100%) 的数据，保证 (2 \leq n \leq 5 \times 10 ^ 5)，(0 \leq a _ i, b _ i \leq 10 ^ 9)。

| 测试点编号 | 特殊限制 | | :----------: | :----------: | | (1 \sim 2) | (n \leq 10)，(a _ i, b _ i \leq 200) | | (3) | (a _ i = i) | | (4 \sim 5) | (b _ i = 0) | | (6) | 所有 (b _ i) 相同 | | (7 \sim 10) | 无特殊限制 |

解题思路：

对于第 i 个塔台，如果它的通讯范围内有之前的塔台，那么它的通讯范围就可以扩展到该塔台的通讯范围内。

假设第 i 个塔台的通讯范围是 [l, r]，其中 l = a[i] - b[i], r = a[i] + b[i]。遍历之前的塔台，如果某个塔台的位置在 [l, r] 范围内，那么该塔台的通讯范围可以扩展到 [l, r]。

因此，我们可以使用一个数组 dp 来记录每个塔台的通讯范围。dp[i] 表示第 i 个塔台的通讯范围。

初始时，dp[1] = [a[1] - b[1], a[1] + b[1]]。

从第 2 个塔台开始，对于第 i 个塔台，我们遍历之前的塔台，如果某个塔台的位置在 dp[i] 范围内，那么该塔台的通讯范围可以扩展到 dp[i]。

最后，我们求出 dp[n] 的范围长度，即为所需的最小电压。

时间复杂度分析

计算 dp 数组需要遍历 n 个塔台，对于每个塔台，需要遍历之前的塔台。因此，时间复杂度为 O(n^2)。

空间复杂度分析

需要一个数组 dp 来保存每个塔台的通讯范围，因此，空间复杂度为 O(n)。

代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    vector<pair<int, int>> dp(n + 1);
    dp[1] = {a[0] - b[0], a[0] + b[0]};
    for (int i = 2; i <= n; i++) {
        dp[i] = {a[i - 1] - b[i - 1], a[i - 1] + b[i - 1]};
        for (int j = 1; j < i; j++) {
            if (a[i - 1] >= dp[j].first && a[i - 1] <= dp[j].second) {
                dp[i].first = dp[j].first;
                dp[i].second = dp[j].second;
                break;
            }
        }
    }
    cout << dp[n].second - a[n - 1] << endl;
    return 0;
}

优化策略：

由于我们需要频繁地判断一个数是否在某个区间内，可以使用二分查找来优化时间复杂度。具体做法是：

使用一个数据结构来存储每个塔台的通讯范围，例如 set 或者 map。
在遍历每个塔台时，使用二分查找来判断其位置是否在之前的塔台的通讯范围内。

这样，时间复杂度就可以优化到 O(n log n)。

总结：

塔台超频问题是一个典型的动态规划问题，需要利用之前塔台的通讯范围来更新当前塔台的通讯范围。通过合理的设计和优化，可以有效地降低算法的时间复杂度。