传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1237
题目大意：你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配 对。例如A= {5,6,8}，B={5,7,8}，则最优配对方案是5配8, 6配5, 8配7，配对整数 的差的绝对值分别为2, 2, 1，和为5。注意，5配5，6配7，8配8是不允许的，因 为相同的数不 许配对。
题解:先排序，如果没有相同的我们就可以一一对应来求，（自己可以证明一下）。
有相同的的怎么办？我们注意到一点：保证所有 Ai各不相同，Bi也各不相同。
于是我们又有一个不加以证明的结论：我们得出最优解，移动匹配的位数不超过3，于是dp即可.
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#define inf 21000000000000000ll
#define N 1000005
#define ll long long
using namespace std;
int n;
int a[N],b[N];
ll f[N];
int read()
{
int x=; char ch; bool bo=;
while (ch=getchar(),ch<''||ch>'') if (ch=='-') bo=;
while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
if (bo) return -x; return x;
}
ll get(int x,int y)
{
if (x==y) return inf/ ; else return abs(x-y);
}
void solve()
{
f[]=get(a[],b[]);
f[]=min(f[]+get(a[],b[]),get(a[],b[])+get(b[],a[]));
for (int i=; i<=n; i++)
{
f[i]=f[i-]+get(a[i],b[i]);
f[i]=min(f[i],f[i-]+get(a[i],b[i-])+get(a[i-],b[i]));
f[i]=min(f[i],f[i-]+min(get(a[i],b[i-])+get(a[i-],b[i-])+get(a[i-],b[i]),
get(a[i],b[i-])+get(a[i-],b[i])+get(a[i-],b[i-])));
}
if (f[n]>=inf/) printf("-1\n");
else printf("%lld\n",f[n]);
}
int main()
{
n=read();
for (int i=; i<=n; i++)
{
a[i]=read(),b[i]=read();
}
sort(a+,a+n+); sort(b+,b+n+);
solve();
}