CF1898D Absolute Beauty

CF1898D Absolute Beauty

题目链接

题目大意

给定两个长度相等的数组 $a,b$，你可以最多交换一次 $bi,b_j(1 \leq i < j \leq n)$ 的值，使得 $\sum\limits{i=1}^{n}|a_i -b_i|$ 的值最大

思路

$|ai - b_i|$ 可以具体为在数轴上的一条左端点为 $a_i$，右端点为 $b_i$ 的一条线段（$a_i > b_i$ 的情况下），易知 $\sum\limits{i=1}^{n}|a_i -b_i|$ 的值为各个线段的长度和

假设我们交换一次 $b_i,b_j$，那么我们可以得到交换之后的贡献 $|a_i - b_j| + |a_j - b_i| - |a_i - b_i| - |a_j - b_j|$

发挥我们分类讨论的特长

绝对不是因为我懒的写

可以发现当 $a_j > b_i$ 或 $b_j > a_i$ 时，交换才能有贡献，且贡献值为两条线段中间空出的长度的两倍

基于此，我们可以维护所有线段中最小的右端点和最大的左端点，以此让贡献值最大

注意：当维护的两个线段是同一线段时，需要特判（我的代码需要这样），否则贡献值为负数

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=2e5+1;
int awa[maxn],qwq[maxn];
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),l=1e18,r=0,sum=0;
        for(int i=1;i<=n;i++) awa[i]=read();
        for(int i=1;i<=n;i++) qwq[i]=read();
        for(int i=1;i<=n;i++)
        {
            sum+=abs(awa[i]-qwq[i]);
            l=min(l,max(awa[i],qwq[i]));
            r=max(r,min(awa[i],qwq[i]));
        }
        int x=(r-l)*2;
        write(sum+(x>0?x:0)),puts("");
    }
    return _123hh2;
}