BZOJ1237: [SCOI2008]配对

Description

你有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是不允许的，因为相同的数不许配对。

Input

第一行为一个正整数n，接下来是n 行，每行两个整数Ai和Bi，保证所有 Ai各不相同，Bi也各不相同。

Output

输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输出-1。

Sample Input

3
3 65
45 10
60 25

Sample Output

HINT

1 <= n <= 10^5，Ai和Bi均为1到10^6之间的整数。

Solution

考虑对于一个数\(a_i\)，和他配对的肯定是\(b_{i-1},b_{i},b_{i+1}\)（排序后的）。
因为如果\(a_i\)和\(b_i\)相同，那么就需要前驱和后继来配对了。
也就是说，对于一个数\(a_i\)，它的配对情况有且仅有4种。
转移点有限，于是我们可以考虑dp求解。
考虑\(f[i]\)表示前\(i\)个数配对的最小代价。为了方便转移，直接从\(i-1,i-2,i-3\)转移即可，和上面是等价的。
有转移方程如下：
\(f[i] = f[i - 1] + calc(a[i], b[i])\)
\(f[i] = min(f[i], f[i - 2] + calc(a[i], b[i - 1]) + calc(b[i], a[i - 1]))\)
\(f[i] = min(f[i], f[i - 3] + calc(a[i], b[i - 2]) + calc(a[i - 1], b[i - 1]) + calc(a[i - 2], b[i]))\)
\(f[i] = min(f[i], f[i - 3] + calc(a[i], b[i - 1]) + calc(a[i - 1], b[i - 2]) + calc(a[i - 2], b[i]))\)
\(f[i] = min(f[i], f[i - 3] + calc(a[i], b[i - 2]) + calc(a[i - 1], b[i]) + calc(a[i - 2], b[i - 1]))\)
\(calc(x,y)\)返回的是两者相减的绝对值，如果相等返回\(inf\)。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 1000010
int a[N], b[N], n;
ll f[N];

ll calc(int x, int y) {
    if(x == y) return 100000000;
    return abs(x - y);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    f[1] = calc(a[1], b[1]);
    f[2] = min(f[1] + calc(a[2], b[2]), calc(a[1], b[2]) + calc(b[1], a[2]));
    for(int i = 3; i <= n; ++i) {
        f[i] = f[i - 1] + calc(a[i], b[i]); //i
        f[i] = min(f[i], f[i - 2] + calc(a[i], b[i - 1]) + calc(b[i], a[i - 1])); //i和i-1
        //混搭
        f[i] = min(f[i], f[i - 3] + calc(a[i], b[i - 2]) + calc(a[i - 1], b[i - 1]) + calc(a[i - 2], b[i]));//i和i-2
        f[i] = min(f[i], f[i - 3] + calc(a[i], b[i - 1]) + calc(a[i - 1], b[i - 2]) + calc(a[i - 2], b[i]));
        f[i] = min(f[i], f[i - 3] + calc(a[i], b[i - 2]) + calc(a[i - 1], b[i]) + calc(a[i - 2], b[i - 1]));
    }
    cout << f[n] << endl;
}