[CF1513F]Swapping Problem

壹、题目描述 ¶

传送门 to Luogu.

贰、题解 ¶

考虑交换 \(b_i,b_j\) 之后,答案的增加量 \(\Delta\) 有

\[\Delta=\mid a_i-b_j\mid +\mid a_j-b_i\mid -\mid a_i-b_i\mid -\mid a_j-b_j\mid \]

如果我们将 \(a_i,b_i\) 看作是一个 \((a_i,b_i)\) 的区间,一个有 “方向” 的区间 不是向量,如果 \(a_i\le b_i\) 则这个区间向右,否则向左,考虑我们可以怎么理解这个题目?

答案要求每个区间长度之和的最小值,但是你可以执行一次操作,将某两个区间的左端点交换。

对于区间分类讨论:

  • 如果区间是同向的(可以只考虑向右,向左和向右是对称的):
    • 没有交集,显然不优;
    • 有交集但不包含,换了和没换没什么区别;
    • 包含,换了和没换没什么区别;
  • 如果区间是异向的(考虑靠前的向右,靠后的向左):
    • 没有交集,显然不优;
    • 有交集但是不包含,换了会更优,具体减少的部分是相交的部分没有了;
    • 包含,换了会更优,具体减少部分是相交的部分没有了;

综上,我们发现,交换更优只会发生在异向区间,并且,减少的部分都是相交的部分。

假设向右的区间构成的数组为 \(a\),向左的区间构成数组为 \(b\),那么答案就是

\[\sum |a_i|+\sum |b_i|-2\times \max\left\{\sum_{i=1}\sum_{j=1}|a_i\cap b_j|\right\} \]

但是这是 \(\mathcal O(n^2)\) 的,这不行。

考虑将区间按照 \(r\) 从大到小排序后访问,对于第 \(i\) 个区间,找到它之前的异向区间 \(j\)(一定有 \(r_j\ge r_i\))的最小的 \(l_j\),这样可以使得相交的区域变得最大。时间复杂度就变成了 \(\mathcal O(n\log n)\).

叁、参考代码 ¶

const int maxn=2e5;
const int inf=0x3f3f3f3f;

struct node{
    int l, r, t;
    node(){}
    node(int L, int R, int T): l(L), r(R), t(T){}
    inline int operator <(const node rhs) const{
        return r>rhs.r;
    }
}seg[maxn+5];
int n; ll ans;
int a[maxn+5], b[maxn+5];

inline void input(){
    n=readin(1);
    rep(i, 1, n) a[i]=readin(1);
    rep(i, 1, n) b[i]=readin(1);
    rep(i, 1, n){
        if(a[i]>b[i]) seg[i]=node(b[i], a[i], 1);
        else seg[i]=node(a[i], b[i], 0);
        ans+=fab(a[i]-b[i]);
    }
}

int minn[2];
signed main(){
    input();
    sort(seg+1, seg+n+1);
    int t, len=0;
    minn[0]=minn[1]=inf;
    rep(i, 1, n){
        t=seg[i].t;
        if(minn[t^1]<seg[i].r) len=max(len, seg[i].r-max(seg[i].l, minn[t^1]));
        minn[t]=min(minn[t], seg[i].l);
    }
    printf("%lld\n", ans-(len<<1ll));
    return 0;
}

肆、用到 の Trick

遇到绝对值的时候,我们能否将它往数轴上面靠?考虑成数轴上面,区间之间的操作?

称之为 “数轴法” 或许还恰当?

上一篇:react+d3 | problem 2(或与作用域相关)


下一篇:我的编程之路刷题⑦:Problem 2719.--约瑟夫问题