CF875E Delivery Club(数据结构优化dp)题解

发布于 2021-01-06  634 次阅读


本文同步发表在我的洛谷博客

题面(Luogu)

题目大意:

两个快递员初始在 $s1$ , $s2$ 位置,给定 $n$ 个位置,每次从两人中选择一人移动到给定位置,求两人最大距离最小值。
数据范围: $ 1\le n \le 10^5 $

解题思路:

从最大距离最小我们显然可以看出这是 二分 ( $O(n^2)$ 的 $dp$ 我就不说啦,相信来做紫题的各位都会)。

我们外层二分答案,对于每次 $check$ 考虑用 $f[i][j]$ 表示前 $i$ 个订单,另外一个人在 $j$ 的方法是否可行(邮递员问题,通常保存不同邮递员的位置,都是经验),也就是说 $f[i][j]$ 是一个为 $0$ 或 $1$ 的值。

那么我们就有:$dp[i+1][j]=dp[i+1][j]$ $or$ $dp[i][j]$ (满足 $|a[i]-a[i+1]| \le mid $),$dp[i+1][i]=dp[i+1][i]$ $or$ $dp[i][j] $ (满足 $|a[j]-a[i+1]| \le mid $) 。

我们考虑如何优化它。一种可行的方法是利用 $set$ 减少状态数。当然,这道题用线段树也可以,在这里就不讲了,有兴趣的同学可以自己思考。

由于上面转移方程的限制,我们可以在 $set$ 中维护满足条件的状态,每次递推 $a[i]$ 时判断是否有满足的状态可以转移过来(即 $set$ 为不为空)。这样因为每次 $check$ 每个值只会进出 $set$ 一次,一次 $check$ 的均摊复杂度为 $O(n log n)$,算上二分的 $O(log w)$ (w 为值域) ,总复杂度为 $O(n log n log w)$ 。

Code(带注释):

#include<bits/stdc++.h>
using namespace std;
const int inf=1000000005;
const int N=100005;

int n,Startx,Starty,ans;
int a[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline bool check(int mid){
    set <int> s;
    s.insert(Startx);       //插入初始的值
    s.insert(Starty);
    for (int i=1;i<=n;i++){
        while ((!s.empty()) && (abs(*s.begin()-a[i])>mid))       //从左侧删去 set 中的不合法状态
            s.erase(s.begin());
        while ((!s.empty()) && (abs(*(--s.end())-a[i])>mid)) //从右侧删去 set 中的不合法状态
            s.erase((--s.end()));       //注意此处 set 最右端的值为 *(--s.end()) 而不是 *s.end() 
        if (s.empty()) return false;
        s.insert(a[i]);     //此时把 a[i] 这个点塞入 set 中,等待下一轮的判断(如果 a[i] 不合法会被删除掉)
    }
    return true;
}

int main(){
    //freopen("CF875E.in","r",stdin);
    //freopen("CF875E.out","w",stdout);
    n=read(),Startx=read(),Starty=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    int l=abs(Startx-Starty),r=inf;     //注意这里 l 值的设定为满足初始距离的 (Startx-Starty)
    while (l<=r){
        int mid=(l+r)>>1;
        if (check(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}
这么详细的博客,不点个赞吗(小声)。

我们无法选择过去,但我们可以改变未来。