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

Martian148 / 2024-02-05 / 原文

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;
}