【题目描述】
你有$n$个整数$A_i$和$n$个整数$B_i$。你需要把它们配对,即每个$A_i$恰好对应一 个$B_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$行,每行两个整数$A_i$和$B_i$,保证所有$A_i$各不相同,$B_i$也各不相同。
【输出格式】
输出一个整数,即配对整数的差的绝对值之和的最小值。如果无法配对,输出$-1$。
【数据范围】
$1 \le n \le 10^5$,$A_i$和$B_i$均为$1$到$10^6$之间的整数。
关于此题
没想到吧!又是DP
首先 先对$A,B$数组进行排序。如果没有限制条件的话,明显最优解就是排序后的每个A[i]和每个B[i]配对。
加上限制条件之后
对于某个位置$i$
$1.$如果$A[i-1] = B[i-1]$那么我们可以让$A[i-1]$和$B[i]$配对,让$A[i]$和$B[i-1]$配对。
$2.$如果$A[i-1] = B[i-1]$且$A[i-2] = B[i-2]$那就可以让$A[i-2], B[i-1]$,$A[i-1], B[i]$,$A[i], B[i-2]$分别配对
或是让$A[i-2], B[i]$,$A[i-1], B[i-2]$,$A[i], B[i-1]$分别配对
$3.$如果有更多连续相等的,都可以把它们转化成上面的两种情况进行处理,不需要再分开考虑
得到转移方程为
$dp[i] = min(dp[i-1] + calc(A[i], B[i]), dp[i-2] + calc(A[i-1], B[i]) + calc(A[i], B[i-1]), dp[i-3] + calc(A[i-2], B[i-1]) + calc(A[i-1], b[i]) + calc(A[i], b[i-2]), dp[i-3] + calc(A[i-2], B[i]) + calc(A[i-1], b[i-2]) + calc(A[i], b[i-1]))$;
$calc(x, y)$在$x = y$时返回无穷大。
【代码】
1 |
|