题解：P14774 [ICPC 2024 Seoul R] Street Development

· · 题解

题意

数轴上有 n 个小机器人，初始位置为 p_1,p_2,\cdots,p_n，每个小机器人有初始 P 点电量，小机器人向左或向右移动一个单位需要 1 单位电量。

每个小机器人有独一无二的信息，两个小机器人在同样的整数坐标时信息会合并，求最后能使得某个机器人拥有所有信息需要的最小初始电量。

题解

首先两个机器人一旦相遇，剩余电量低的就不用动了。

我最开始想的策略是最左侧的机器人从左往右合并信息，和其它小机器人相遇时相当于补充电量。这样答案为 \max {(p_i-p_{i-1})}。但是显然样例都过不去。

问题出在机器人可以折返跑。二分初始电量 P，让小机器人走完 P 格后还没到下一个点的话让下一个小机器人来接，花费 \max {(a_i-ml_{i-1})} 的代价，其中 ml_i 是收集完第 i 条信息后用完剩余电量能走到的最远距离，我们有 ml_i=a_i+P-2\max{(a_i-ml_{i-1},0)}（减掉的那一坨是机器人折返跑消耗的电量，一来一回所以要翻倍）。检查能否到达最后一个小机器人即可。

但是这样还是会假，答案会莫名其妙多 1。最后检查发现是我们可以让最右边的小机器人从右往左跑一段，然后让左右两个小机器人在中间相遇，这样也许更优。所以再维护 mr_i=a_i-P+2\max{(mr_{i-1}-a_i)}（减掉的这一坨也是机器人折返跑消耗的电量）。看看是否有 ml_i \ge mr_{i+1}（在 i 和 i+1 中间相遇）即可。

对于不可能达到的情况，ml,mr 记得赋极值，只需要让等式不成立即可，分别赋 -\infty,\infty。

代码

#include<iostream>
#include<vector>
using namespace std;
long long a[2000001];
long long L;
int n;
long long ml[2000001],mr[2000001];
bool check(int P){
    ml[1]=P;
    for(int i=2;i<=n;i++){
        if(a[i]>ml[i-1]+P){
            ml[i]=-L-1;
        } else{
            ml[i]=a[i]+P-2*max(0ll,a[i]-ml[i-1]);
        }
    }
    mr[n]=L-P;
    for(int i=n-1;i>=1;i--){
        if(a[i]<mr[i+1]-P){
            mr[i]=L+1;
        } else{
            mr[i]=a[i]-P+2*max(0ll,mr[i+1]-a[i]);
        }
    }
    for(int i=1;i<n;i++){
        if(mr[i+1]<=ml[i]){
            return true;
        }
    }
    return false;
}
int main(){
    cin >> L >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    int l=0,r=L;
    while(l<r){
        auto mid=(l+r)>>1;
        if(check(mid)){
            r=mid;
        } else{
            l=mid+1;
        }
    }
    cout << r;
    return 0;
}