题目描述

你有 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;
}
12-27 18:09