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

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

题目分析

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

if(a[i]>r)
{
	k=max(a[i]-r,k);
}
r=max(r,a+b);

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

Code

#include <bits/stdc++.h>
using namespace std;
int a, b, c, n, r, ans;
int main(){
    cin >> n;
    for (int i=0;i<n;i++){
        cin>>a>>b;
        if(a>r&&i){
            ans=max(ans,a-r);
        }
        r=max(r,a+b);
    }
    cout<<ans;
    return 0;
}