题意
给定 \(2n\) 个点，第 \(i(1\le i\le n)\) 个点的点权为 \(a_i\)，第 \(j(n<j\le 2n)\) 个点的点权为 \(b_i\)，对于每个 \(i,j(1\le i\le n<j\le 2n)\)，在 \(i,j\) 间连一条边，边权为 \(|a_i-b_j|\)。定义一条路径的权值为经过的边的边权之和，求权值最大的哈密顿回路。
\(n\le10^5\)
分析
绝对值符号很烦，考虑去掉绝对值符号。由于权值和要求最大化，那么若绝对值内的值取负数的话答案一定不优。这样我们就可以把绝对值扔掉了，原题转化为，给这 \(2n\) 个数定 \(n\) 个正号 \(n\) 个负号，且存在一种合法的匹配方案。
令 \((+,-)\) 表示 \(a_i\) 取正，\(b_i\) 取负，\((-,+),(-,-),(+,+)\) 同理。
手玩一下可以发现，合法匹配方案存在当且仅当：
- 全是 \((+,-)\) 或全是 \((-,+)\)
- \((+,+),(-,-)\) 同时存在至少一个且数量相等
考虑怎么维护这个东西。钦定一开始全是 \((-,+),(+,-)\)，那么此时权值和就是每个点选 \((+,-)\) 或者 \((-,+)\) 的较大值，即 \(|a_i-b_i|\)。然后考虑不断的把 \((+,-),(-,+)\) 换成 \((-,-),(+,+)\)，我们维护两个优先队列，一个存变成 \((+,+)\) 的最大收益，一个存变成 \((-,-)\) 的最大收益，每次直接取堆顶第一个没有被使用过的然后将它变成 \((+,+),(-,-)\) 即可。
考虑到如果一个数被转成 \((+,+)\)，则当它又出现在 \((-,-)\) 的堆顶上时，将这个数变成 \((-,-)\) 是不优的，反之亦然，所以上述贪心正确性成立。
选为 \((+,+)\) 的时候的贡献是 \(2\min(a_i,b_i)\)，\((-,-)\) 的贡献是 \(-2\max(a_i,b_i)\)，若变成 \((-,-)\)，贡献为 \(2\min(a_j,b_j)-2\min(a_i,b_i)-2\max(a_i,b_i)\)，考虑到当前 \((+,+)\) 堆顶的 \(\min(a_j,b_j)\le min(a_i,b_i)\le \max(a_i,b_i)\)，所以增量 \(\le 0\)，故不优。
当两个堆顶是同一个元素时，此时同时替换的贡献 \(2\min(a_i,b_i)-2\max(a_i,b_i)\le 0\)，一定不优，但如果此时还没有选过数，就可能不满足合法条件，此时取两个堆的次大值算一算取最大值即可。
时间复杂度 \(O(n\log n)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define IOS ios::sync_with_stdio(false)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define un using namespace
#define popc __builtin_popcountll
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
inline auto rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
template<typename T>
inline void write(T x,char ch='\n'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=2e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n;
struct o{
int a,b,c,d;
}a[maxn];
priority_queue<pii>qmx;
priority_queue<pii>qmn;
bool vis[maxn];
void fitter(){
while(!qmx.empty()&&vis[qmx.top().se])qmx.pop();
while(!qmn.empty()&&vis[qmn.top().se])qmn.pop();
}
inline void solve_the_problem(){
n=rd();
rep(i,1,n){
a[i].a=rd(),a[i].b=rd();
a[i].c=a[i].a+a[i].b,a[i].d=abs(a[i].a-a[i].b);
}
int ans=0,sum=0;
rep(i,1,n)sum+=a[i].a-a[i].b;
ans=max(ans,sum);
sum=0;
rep(i,1,n)sum+=a[i].b-a[i].a;
ans=max(ans,sum);
int res=0;
rep(i,1,n)res+=a[i].d,qmx.push(mp(a[i].c-a[i].d,i)),qmn.push(mp(-a[i].c-a[i].d,i));
while(1){
fitter();
if(qmx.empty()||qmn.empty())break;
if(qmx.top().se!=qmn.top().se){
pii nw1=qmx.top(),nw2=qmn.top();
qmx.pop(),qmn.pop();
res+=nw1.fi+nw2.fi,vis[nw1.se]=vis[nw2.se]=1;
ans=max(ans,res);
continue;
}
pii nw1=qmx.top(),nw2=qmn.top();qmx.pop(),qmn.pop();
fitter();
if(qmx.empty()||qmn.empty())break;
ans=max(ans,res+max(qmx.top().fi+nw2.fi,qmn.top().fi+nw1.fi));
break;
}
write(ans);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;
while(_--)solve_the_problem();
}
/*
*/