Steven_Meng's Blog

传送门

假设没有不允许两个相同的数配对的条件，那么直接将$AB$数组排序一遍，每一位每一位配对即可。

现在不允许两个相同的数配对，还是考虑贪心，如果出现如图的匹配情况，即$a[i]$和$b[i-alb]$匹配，其中$alb>2$。

发现这种情况肯定不是最优的，因为我们发现一定存在一个$a[j](j \le i-1)$和$b[k](k > i-alb)$匹配，简单的来说，就是匹配的两条直线相交，可以构造出一种更优的情况如下图。

所以我们只用考虑连续$3$个数，后面大力$dp$即可。

#include <bits/stdc++.h>
#define MAXN 100005
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int A[MAXN],B[MAXN],dp[MAXN];
inline int f(int a,int b){
    if (a==b) return INF;
    else return (a>b)?(a-b):(b-a);
}
#undef int
int main(){
#define int long long
    int n=read();
    for (register int i=1;i<=n;++i){
        A[i]=read(),B[i]=read();
    }
    if (n==1&&A[1]==B[1]){
        printf("-1\n");
        return 0;
    }
    sort(A+1,A+1+n);
    sort(B+1,B+1+n);
    dp[0]=0;
    for (register int i=1;i<=n;++i){
        dp[i]=dp[i-1]+f(A[i],B[i]);
        if (i>=2){
            dp[i]=min(dp[i],dp[i-2]+f(A[i],B[i-1])+f(A[i-1],B[i]));
        }
        if (i>=3){
            dp[i]=min(dp[i],dp[i-3]+f(A[i],B[i-1])+f(A[i-1],B[i-2])+f(A[i-2],B[i]));
            dp[i]=min(dp[i],dp[i-3]+f(A[i-1],B[i])+f(A[i-2],B[i-1])+f(A[i],B[i-2]));
        }
    }
    printf("%lld\n",dp[n]);
}