如果没有“配对数字不相同”的限制，将 \(a,b\) 数组排序后一 一配对就能得到最小值。
回到原题，考虑一种极端情况，\(\forall i\in [1,n],a_i=b_i\) 即排序后全等。
若 \(n\) 为偶数，一种显然的构造方法是：
1 2 3 4 5 6
2 1 4 3 6 5
即分成两个两个一组，然后组内交换，这样跨越幅度最小，因此最终得出答案最小。
若 \(n\) 为奇数，两个一组显然不行，引入三个一组，比如 1 2 3 可对应 3 1 2 和 2 3 1，一定可以得到答案。
但是不需要引入四个一组，因为必然可以拆成“两个+两个”的模式。
回到原问题，设 \(f_i\) 表示前 \(i\) 个元素的答案，那么转移有：
- \(a_i\) 与 \(b_i\) 配对，\(f_{i-1} \rightarrow f_i\)
- \(a_i,a_{i-1}\) 与 \(b_i,b_{i-1}\)，\(f_{i-2} \rightarrow f_i\)
- \(a_i,a_{i-1},a_{i-2}\) 与 \(b_i,b_{i-1},b_{i-2}\)，\(f_{i-3} \rightarrow f_i\)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,a[N],b[N];
LL f[N];
LL calc(int p) {
vector<int> c;
LL minn=1e18;
c.push_back(b[p-2]); c.push_back(b[p-1]); c.push_back(b[p]);
do {
if(c[0]!=a[p]&&c[1]!=a[p-1]&&c[2]!=a[p-2]) {
minn=min(minn,abs(c[0]-a[p])*1ll+abs(c[1]-a[p-1])+abs(c[2]-a[p-2]));
}
} while(next_permutation(c.begin(),c.end()));
return minn;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n);
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++) {
if(i>=3)f[i]=calc(i)+f[i-3];
if(a[i]!=b[i]) f[i]=min(f[i],f[i-1]+abs(a[i]-b[i]));
if(i>=2&&(a[i]==b[i]||a[i-1]==b[i-1])) f[i]=min(f[i],f[i-2]+abs(a[i]-b[i-1])+abs(a[i-1]-b[i]));
}
cout<<f[n];
return 0;
}