自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:15:11，当前版本为作者最后更新于2023-07-16 21:08:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 7 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

$n$ 座塔台，分别处于 $a _ 1, a _ 2, \cdots, a _ n$ 位置，初始时有 $b _ 1, b _ 2, \cdots, b _ n$ 的通讯半径。可以指定一个非负整数电压 $k$，使得所有塔台通讯半径增大 $k$。求要使信号从 $1$ 号塔台依次经过 $2, 3, \cdots$ 号塔台到达 $n$ 号塔台，$k$ 的最小值。

题目分析

由于信号是依次传递，因此我们只需要考虑相邻两座塔台的通讯情况即可。

我们设第 $i$ 座塔台和第 $i + 1$ 座塔台之间的距离 $d _ i = a _ {i + 1} - a _ i$。如果 $d _ i \leq b _ i$，那么无需施加电压，信号也可从第 $i$ 座塔台顺利传输到第 $i + 1$ 座塔台；反之，在此处需要施加的最小电压则为 $k _ i = d _ i - b _ i$。

由于题目要求所有塔台施加的电压一致，因此我们的答案即为所有塔台的 $k _ i$ 的最大值。

因此，读入数据后，我们需要从头枚举计算 $d _ i$，并与 $b _ i$ 作比较，进行上述取最大值的计算。最终输出得到的最大值即可。

核心代码：

cin >> n;
for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
}
int k = 0;
for (int i = 1; i <= n - 1; ++i) {
    int d = a[i + 1] - a[i];
    if (b[i] >= d) continue;
    k = max(k, d - b[i]);
}
cout << k << endl;

视频讲解