题目描述
你有 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是不允许的，因为相同的数不许配对。
输入输出格式
输入格式：
第一行为一个正整数n，接下来是n 行，每行两个整数Ai和Bi，保证所有
Ai各不相同，Bi也各不相同。
输出格式：
输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输
出-1。
输入输出样例
输入样例#1：
3
3 65
45 10
60 25
输出样例#1：
32
输入样例#2：
3
5 5
6 7
8 8
输出样例#2：
5
说明
30%的数据满足：n <= 104
100%的数据满足：1 <= n <= 105，Ai和Bi均为1到106之间的整数。
先排序
这是能保证解最优的情况
当大于四个时，把它拆分成以上情况，为什么没有以下情况？
O O O O
O O O O
显然这样没有一下情况优
O O O O
O O O O
所以说明了只要讨论以上四种情况就可以保证最优
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long a[],b[],f[],inf;
int n;
long long cal(int x,int y)
{
if (x==y) return inf;
return abs(x-y);
}
int main()
{int i;
cin>>n;
for (i=;i<=n;i++)
{
scanf("%lld%lld",&a[i],&b[i]);
}
sort(a+,a+n+);
sort(b+,b+n+);
memset(f,/,sizeof(f));
inf=f[];
f[]=;
f[]=min(inf,cal(a[],b[]));
f[]=min(inf,min(f[]+cal(a[],b[]),cal(a[],b[])+cal(a[],b[])));
cout<<f[]<<endl<<f[]<<endl;
for (i=;i<=n;i++)
{
long long tmp=inf;
tmp=min(tmp,f[i-]+cal(a[i],b[i]));
tmp=min(tmp,f[i-]+cal(a[i],b[i-])+cal(a[i-],b[i]));
tmp=min(tmp,min(f[i-]+cal(a[i-],b[i])+cal(a[i-],b[i-])+cal(a[i],b[i-]),f[i-]+cal(a[i],b[i-])+cal(a[i-],b[i])+cal(a[i-],b[i-])));
f[i]=tmp;
//cout<<f[i]<<endl;
}
if (f[n]>=inf) cout<<-;
else
cout<<f[n];
}