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之间的整数。

题解

首先将输入排序。

我们发现，在满足要求的情况下，不交叉的配对总比交叉配对优。

那么，我们观察$n=4$的情况。

可以发现，$a_4$不会与$b_1$配对，因为这样配对的最优策略是$a_1-b_2, a_2-b_3, a_3-b_4, a_4-b_1$，

那么有3种交换会使答案更优（如果它们满足条件）：

1. $a_1-b_1, a_4-b_2$

2. $a_2-b_1, a_4-b_3$

3. $a_3-b_1, a_4-b_4$

由于$b_1$只会和$a$中最多一个数相同，$a_4$同理，所以三种方案中必有一种合法。

将其推广，我们得到：

$a_i$不会和$b_j$配对，如果$i > j + 2$或$i < j - 2$。

那么就可以dp了（枚举后三个、后两个、后一个的配对方案）。

附代码：

#include <algorithm>
#include <cctype>
#include <cstdio>
using std::min;
typedef long long LL;
LL INF = 1000000000000000LL;
const int N = 100050;
inline int readInt() {
  int ans = 0;
  char c;
  do c = getchar(); while (!isdigit(c));
  while (isdigit(c)) {
    ans = ans * 10 + c - '0';
    c = getchar();
  }
  return ans;
}
LL A[N], B[N];
LL f[N];
inline LL cost(int i, int j) {
  if (A[i] == B[j]) return INF;
  return std::abs(A[i] - B[j]);
}
int main() {
  int n = readInt();
  for (int i = 1; i <= n; ++i) {
    A[i] = readInt();
    B[i] = readInt();
  }
  if (n == 1 && A[1] == B[1]) return puts("-1"), 0;
  std::sort(A + 1, A + n + 1);
  std::sort(B + 1, B + n + 1);
  f[0] = 0;
  for (int i = 1; i <= n; ++i) {
    f[i] = f[i - 1] + cost(i, i);
    if (i > 1) f[i] = min(f[i], f[i - 2] + cost(i, i - 1) + cost(i - 1, i));
    if (i > 2) {
      f[i] = min(f[i], f[i - 3] + cost(i, i - 2) + cost(i - 1, i - 1) + cost(i - 2, i));
      f[i] = min(f[i], f[i - 3] + cost(i, i - 2) + cost(i - 1, i) + cost(i - 2, i - 1));
      f[i] = min(f[i], f[i - 3] + cost(i, i - 1) + cost(i - 2, i) + cost(i - 1, i - 2));
    }
  }
  printf("%lld
", f[n]);
  return 0;
}