CF1898D Absolute Beauty - CF题解 | 123hh2 = Keep moving forward

# CF1898D Absolute Beauty

题目链接

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

$|a_i - 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;
	}