【题目描述】
你有(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)时返回无穷大。
【代码】
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll n, a[100005], b[100005], dp[100005];
inline ll _abs(ll x) {
return x < 0 ? -x : x;
}
inline ll calc(ll a, ll b) {
if (a == b) return inf;
else return _abs(a - b);
}
int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld", &a[i], &b[i]);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
dp[1] = calc(a[1], b[1]);
dp[2] = min(dp[1] + calc(a[2], b[2]), calc(a[1], b[2]) + calc(a[2], b[1]));
for (int i = 1; i <= n; i++) {
dp[i] = inf;
dp[i] = min(dp[i], dp[i-1] + calc(a[i], b[i]));
dp[i] = min(dp[i], dp[i-2] + calc(a[i-1], b[i]) + calc(a[i], b[i-1]));
dp[i] = min(dp[i], dp[i-3] + min(calc(a[i-2], b[i-1]) + calc(a[i-1], b[i]) + calc(a[i], b[i-2]), calc(a[i-2], b[i]) + calc(a[i-1], b[i-2]) + calc(a[i], b[i-1])));
}
if (dp[n] >= inf) puts("-1");
else printf("%lld
", dp[n]);
return 0;
}