CF1566F Points Movement 题解

· · 题解

CF1566F Points Movement

老套路了，线段只有相交没有包含，包含的只需满足较小的那条就行了，这样线段的端点就单增。

当然，现在已经有点被包含的线段也不用算了！

这样就只剩一堆单调的线段和一堆点交替出现，我们加两个虚点坐标为 \pm inf，方便算一点。

我们可以花费 1 的代价移动某个点，最终使得每条线段上都有曾有点经过。

一个点的走法有四种：

  1. 只向左走
  2. 只向右走
  3. 向左走一段，原路返回后向右走
  4. 向右有一段，原路返回后向左走

但其实只用考虑情况 3,4 因为情况 1,2 等价于向反方向走了长度为 0 的一段再折回。

更一般，这两种情况其实可以一起取 \min。

如果我们记 f_{i,j} 为考虑到第 i 个点，向右最远走到了线段 j 的最少操作数，考虑到每一个点向右到下一个点左端的的线段数是连续的一段，所以均摊下只有 m 规模的状态，开一个 2D 的状态太浪费了！

考虑每个点的移动一定在上一个点与这一个点的范围内，所以我们只考虑它一开始向左/右走，同时我们采用贡献转移的思路，将往右走的贡献”送“给右端的点。

记 f_{i,0/1} 为考虑到第 i 个点，一开始走的方向为左/右的最小操作次数，我们枚举上一个点向右走到的线段位置，则有状态转移方程：

f_{i,0}=\min\limits_{k\And l_k,r_k\in(a_{i-1,a_i})}\min{\{f_{i-1,0}+dis(a_{i-1},l_{k-1})+2\times dis(r_k,a_i),f_{i-1,1}+2\times dis(a_{i-1},l_{-1})+2\times dis(r_k,a_i)\}} f_{i,1}=\min\limits_{k\And l_k,r_k\in(a_{i-1,a_i})}\min{\{f_{i-1,0}+dis(a_{i-1},l_{k-1})+ dis(r_k,a_i),f_{i-1,1}+2\times dis(a_{i-1},l_{k-1})+ dis(r_k,a_i)\}}

答案为 \min{\{f_{n+1,0},f_{n+1,1}\}}

时间复杂度为 O(N\log N)，瓶颈在于给点和线段排序以及一开始的二分判断。

CODE：

struct Line{
    int l,r;
};
void solve(){
    int n,m;
    read(n,m);
    LL a[n+10];LL f[n+10][2];
    rep(i,1,n) read(a[i]);
    a[0]=-inf,a[n+1]=inf;
    sort(a,a+2+n);
    vector<Line> b; int l,r;
    repp(i,0,m){
        read(l,r);
        if(lower_bound(a,a+2+n,l)==upper_bound(a,a+2+n,r)) b.pb(Line{l,r});
    }
    auto cmp=[](Line x,Line y){
        return (x.r^y.r)?x.r<y.r:x.l>y.l;
    };
    sort(b.begin(),b.end(),cmp);
    repp(i,1,b.size()){
        if(b[i].l<=b[i-1].l||b[i].r==b[i-1].r){
            b.erase(b.begin()+i);
            --i;
        }
    }
    rep(i,1,n+1) f[i][0]=f[i][1]=INF;
    f[0][0]=f[0][1]=0;
    int now=0;
    auto min=[](LL a,LL b){
        return (a<b)?a:b;
    };  vector<LL> cl,cr;
    rep(i,1,n+1){
        cl.pb(a[i-1]);
        while(now<b.size()&&b[now].r<a[i]){
            cr.pb(b[now].r);
            cl.pb(b[now].l);
            ++now;
        }
        cr.pb(a[i]);
        repp(j,0,cl.size()){
            LL disl=cl[j]-a[i-1],disr=a[i]-cr[j];
            f[i][0]=min(f[i][0],f[i-1][0]+disl+2*disr);
            f[i][0]=min(f[i][0],f[i-1][1]+2*disl+2*disr);
            f[i][1]=min(f[i][1],f[i-1][0]+disl+disr );
            f[i][1]=min(f[i][1],f[i-1][1]+2*disl+disr);
        }
        cl.clear(),cr.clear();
    } 
    write(min(f[n+1][1],f[n+1][0]),'\n');
}