你有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。

30%的数据满足：n <= 10^4 100%的数据满足：1 <= n <= 10^5，Ai和Bi均为1到106之间的整数。

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #define LL long long 7 using namespace std; 8 const int inf=1e9; 9 const int mxn=100010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 inline int CP(int a,int b){return (a==b)?inf:abs(a-b);}17 int n;18 int a[mxn],b[mxn];19 LL f[mxn];20 int main(){21 //    freopen("in.txt","r",stdin);22     int i,j;23     n=read();24     for(i=1;i<=n;i++){25         a[i]=read();b[i]=read();26     }27     sort(a+1,a+n+1);sort(b+1,b+n+1);28     memset(f,0x3f,sizeof f);29     f[0]=0;30     f[1]=CP(a[1],b[1]);31     f[2]=min(CP(a[1],b[1])+CP(a[2],b[2]),CP(a[1],b[2])+CP(a[2],b[1]));32     for(i=3;i<=n;i++){33         f[i]=min(f[i-1]+CP(a[i],b[i]),f[i-2]+CP(a[i-1],b[i])+CP(a[i],b[i-1]));34         f[i]=min(f[i],f[i-3]+CP(a[i],b[i-1])+CP(a[i-1],b[i-2])+CP(a[i-2],b[i]));35         f[i]=min(f[i],f[i-3]+CP(a[i],b[i-2])+CP(a[i-1],b[i-1])+CP(a[i-2],b[i]));36         f[i]=min(f[i],f[i-3]+CP(a[i],b[i-2])+CP(a[i-1],b[i])+CP(a[i-2],b[i-1]));37     }38     if(f[n]>=0x3f3f3f3f3f3f3f)f[n]=-1;39     printf("%lld\n",f[n]);40     return 0;41 }