Luogu-P9455-入门赛-14-塔台超频-Hard-Version-题解

看到讨论区都是二分，实际上这道题用贪心来写非常简单

题目分析#

首先将当前塔台的位置加上通讯距离（即 $a+b$ ）看作为右边界，通过题目不难得出一个贪心策略：如果当前塔台 $i$ 能到达的最右边界比往后的塔台 $i+m$ 位置还要靠右，就可以忽略塔台 $i+1$ 到 $i+m$ 。转化一下，我们只需要每次记录可以到达的最右边界，如果当前塔台的位置不在最右边界的范围内，就可以更新答案取超频的最大值。因此，我们可以用 $ans$ 来储存答案， $r$ 作为最右边界，计算过程就是：

1
if(a[i]>r)
2
{
3
  k=max(a[i]-r,k);
4
}
5
r=max(r,a+b);

因为是逐个处理，所以在输入时就可以完成计算，代码量极少。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
int a, b, c, n, r, ans;
4
int main(){
5
    cin >> n;
6
    for (int i=0;i<n;i++){
7
        cin>>a>>b;
8
        if(a>r&&i){
9
            ans=max(ans,a-r);
10
        }
11
        r=max(r,a+b);
12
    }
13
    cout<<ans;
14
    return 0;
15
}