CF1898D 题解

mountain_climber · 2023-12-07 12:27:08 · 题解

先说突破点：将绝对值转换为数轴上的线段长度（距离）。

我们来考虑一下怎么做。

首先我们只能进行一次操作，具体来说一次操作是这样的：

• 操作对象：两条线段，分别为 [a_{i},b_{i}] 和 [a_{j},b_{j}]。
• 操作内容：将其转变为两条线段，分别为 [a_{i},b_{j}] 和 [a_{j},b_{i}]。

随后题意变成使操作过后增加尽量多的长度，此处可以开始具体分类讨论了：

情况一：两线段没有公共部分。

可以发现这种情况下不管怎么分配 [a_{i},a_{j},b_{i},b_{j}] 都会为答案贡献两倍的两个线段的中间部分长度。

情况二：相交但是没有包含关系。

可以发现这种情况下最好也只能使得变化前后的总长度保持不变，没有意义。

情况三：一个线段被另一个线段所包含。

可以发现这种情况下和情况二基本相同，也是没有意义的。

也就是说唯一有意义的操作就是情况一，现在问题就最终转变为了找到一组线段使其中间部分长度最长，其实就是找到最右的左端点和最左的右端点。

注意如果没有情况一就不做操作。

最后粘一下代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int n,a[N],b[N];
void ipt(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
}
void solve(){
    int l=inf,r=0,ans=0;
    for(int i=1;i<=n;i++) ans+=abs(a[i]-b[i]); 
    for(int i=1;i<=n;i++){
        l=min(l,max(a[i],b[i]));
        r=max(r,min(a[i],b[i]));
    }
    printf("%lld\n",ans+(2*(r-l)>0?2*(r-l):0));
}
signed main(){
    int t;
    scanf("%lld",&t);
    while(t--){
        ipt();
        solve();
    } 
    return 0;
} 

AC记录