Question

2024牛客寒假算法基础集训营1 J 又鸟之亦心

Solution

挺好的一个题，给了我很多启发

显然，先二分最大值 \(D\) ，关键在于 \(check\) 怎么写

考虑到两个人是相对的，第 \(i\) 次之后肯定有一个人在 \(a_i\)，具体是谁不重要，也不需要关注是怎么走过来的，我们需要去维护另外一个人可能在的位置的集合 \(S\)

显然，另外一个人只能在 \([a_i-D,a_i+D]\) 范围内，如果现在的 \(S\) 中一些数不满足这个范围就从集合中删去

然后考虑要不要把 \(a_i\) 放到这个集合中，也就是说，下一个数 \(a_{i+1}\) 是需要这个人走过去，还是另外一个人走过去

如果 \(a_i\) 和 \(a_{i+1}\) 的距离小于 \(D\) 的话，那另外一个人走过去也可以，那就把 \(a_i\) 丢到集合中

如果某个时刻 \(S\) 为空了，那么说明不可能满足 \(check\) 失败

Code

#include<bits/stdc++.h>
using namespace std;

int n, x, y;
vector<int> a;

bool check(int d){
    int lst = y;
    set<int> S;
    if(abs(x - y) <= d)
        S.insert(x);
    for(auto x : a){
        if(!S.empty() && abs(x - lst) <= d)
            S.insert(lst);
        while(!S.empty() && *S.begin() < x - d)
            S.erase(S.begin());
        while(!S.empty() && *S.rbegin() > x + d)
            S.erase(*S.rbegin());
        lst = x;
    }
    return !S.empty();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x >> y; a.assign(n,0);
    for(int i=0;i<n;i++) cin >> a[i];
    int L = 0, R = 1e9;
    while(L <= R){
        int mid = (L + R) >> 1;
        if(check(mid))
            R = mid - 1;
        else 
            L = mid + 1;
    }
    cout<< L << '\n';
    return 0;
}