[入门赛 #14] 塔台超频 (Hard Version) - 最小超频电压算法详解 - 常规

[入门赛 #14] 塔台超频 (Hard Version) - 最小超频电压算法详解

题目描述

在一条笔直的马路上有 (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) 号塔台传输到 (n) 号塔台，路径不限（即，无论如何，只需要让信号从 (1) 号塔台到达 (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)。

解题思路

贪心策略: 由于我们需要找到最小的超频电压，我们可以尝试使用贪心策略。从第一个塔台开始，每次都尽可能地选择一个距离当前塔台最远的，且能够被当前塔台覆盖的塔台。
二分查找: 为了快速找到距离当前塔台最远的，且能够被当前塔台覆盖的塔台，我们可以使用二分查找。
维护最大覆盖范围: 在进行二分查找的过程中，我们需要维护一个当前塔台的覆盖范围。每次找到一个新的塔台，就更新当前塔台的覆盖范围。

代码实现

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

const int MAXN = 5e5 + 5;

int n;
int a[MAXN], b[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }

    int now = 1; // 当前塔台
    int ans = 0; // 最小超频电压
    while (now < n) {
        int l = now + 1, r = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (a[mid] <= a[now] + b[now] + ans) { // 能够被当前塔台覆盖
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans = max(ans, a[l] - a[now] - b[now]); // 更新超频电压
        now = l; // 更新当前塔台
    }

    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度：O(n log n)，二分查找的时间复杂度为 O(log n)，循环 n 次，总的时间复杂度为 O(n log n)。
空间复杂度：O(n)，需要存储塔台的位置和初始通讯半径。

测试样例

Test Input Reasoning:

测试最简单的情况，只有两个塔台。

2
1 1
5 0

Expected Output:

Explanation:

第一个塔台的覆盖范围是 [0, 2]，第二个塔台的覆盖范围是 [5, 5]。需要超频 3 个单位，才能使第一个塔台覆盖到第二个塔台。

总结

本题可以使用贪心策略和二分查找来解决。贪心策略可以保证找到最小的超频电压，二分查找可以快速找到距离当前塔台最远的，且能够被当前塔台覆盖的塔台。代码实现简洁高效，复杂度分析清晰明了。

希望本文能够帮助你更好地理解这道题目，并提高你的编程能力。