题目描述
你有 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。
因为一个集合内的数是两两不同的，所以可以由数学直觉得到一个数的配对位置和它最多差3
分类讨论即可，写起来就是有点麻烦
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
#define db double
const int N=1e5+10,inf=1<<30;
int A[N],B[N],dp[N];
#define p(a,b) ((a^b) ? abs(a-b) : inf)
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++)
scanf("%lld%lld",&A[i],&B[i]);
sort(A+1,A+1+n);sort(B+1,B+1+n);
if(A[1]==B[1]&&n==1){cout<<-1<<endl;return 0;}
dp[1]=p(A[1],B[1]);
dp[2]=min(dp[1]+p(A[2],B[2]),p(A[1],B[2])+p(A[2],B[1]));
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+p(A[i],B[i]);
dp[i]=min(dp[i],dp[i-2]+p(A[i],B[i-1])+p(A[i-1],B[i]));
dp[i]=min(dp[i],dp[i-3]+p(A[i],B[i-2])+p(A[i-2],B[i])+p(A[i-1],B[i-1]));
dp[i]=min(dp[i],dp[i-3]+p(A[i],B[i-1])+p(A[i-1],B[i-2])+p(A[i-2],B[i]));
dp[i]=min(dp[i],dp[i-3]+p(A[i],B[i-2])+p(A[i-1],B[i])+p(A[i-2],B[i-1]));
}
cout<<dp[n]<<endl;
}