[SCOI2008] 配对

题目

链接

[SCOI2008]配对

题意简述

有一个 $n \ (n <= 100000)$ 对整数需要配对。

所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。

思路

暴力DP？

一开始我是一头雾水，看了 $dalao$ 博客才知道要分类讨论。
由于我 $markdown$ 技术巨烂，将就看看吧。

与距离为0的数匹配

• $$a_{1} \\ | \\ b_{1}$$

与距离为1的数匹配

• $$\ \ \ \ \ a_{1} \quad a_{2} \\ \quad \backslash \\ \ \ \ \ \ b_{1} \quad b_{2} \\ + a_{2} ~\rightarrow b_{2}$$

与距离为2的数匹配

• $$a_{1} \quad a_{2} \quad a_{3} \\ \backslash \quad \ \backslash \\ b_{1} \quad b_{2} \quad b_{3} \\ + a_{3} ~\rightarrow b_{1} \\$$
• $$a_{1} \quad a_{2} \quad a_{3} \\ / \quad \ / \\ b_{1} \quad b_{2} \quad b_{3} \\ + a_{1} ~\rightarrow b_{3} \\$$
• $$a_{1} \quad a_{2} \quad a_{3} \\ | \\ b_{1} \quad b_{2} \quad b_{3} \\ + a_{1} ~\rightarrow b_{3} \\ + a_{3} ~\rightarrow b_{1} \\$$

与距离为3的数匹配

可以发现最优情况一定是两个与距离为1的数匹配。

• $$a_{1} \quad a_{2} \quad a_{3} \quad a_{4} \\ \backslash \quad \ \ \ \ \ \ \ \ \ \ \backslash \\ b_{1} \quad b_{2} \quad b_{3} \quad b_{4} \\ + a_{2} ~\rightarrow b_{1} \\ + a_{4} ~\rightarrow b_{3} \\$$

分类讨论

所以只有 $5$ 种情况，慢慢递推处理就好。
空间复杂度： $O(n)$ 。

代码

#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e5 + 10, kmax_int = 2147483647, kmod = 1e9+7;

int n;
int n1[kmax_num], n2[kmax_num];
long long f[kmax_num];

int main() {
	std::cin >> n;
	For(i,1,n)	std::cin >> n1[i] >> n2[i];
	std::sort(n1 + 1, n1 + n + 1), std::sort(n2 + 1, n2 + n + 1);
    
	For(i,1,n)	{
		f[i] = f[i - 1]	+ (n1[i] == n2[i] ? 0x3f3f3f3f : abs(n1[i] - n2[i]));

		if(i >= 2 && n1[i - 1] != n2[i] && n1[i] != n2[i - 1])
			f[i] = std::min(f[i], f[i - 2] + abs(n1[i - 1] - n2[i]) + abs(n1[i] - n2[i - 1]));

		if(i >= 3 && n1[i - 2] != n2[i - 1] && n1[i - 1] != n2[i] && n1[i] != n2[i - 2])
			f[i] = std::min(f[i], f[i - 3] + abs(n1[i - 2] - n2[i - 1]) + abs(n1[i - 1] - n2[i]) + abs(n1[i] - n2[i - 2]));

		if(i >= 3 && n1[i - 2] != n2[i] && n1[i - 1] != n2[i - 2] && n1[i] != n2[i - 1])
			f[i] = std::min(f[i], f[i - 3] + abs(n1[i - 2] - n2[i]) + abs(n1[i - 1] - n2[i - 2]) + abs(n1[i] - n2[i - 1]));

		if(i >= 3 && n1[i - 2] != n2[i] && n1[i - 1] != n2[i - 1] && n1[i] != n2[i - 2])
			f[i] = std::min(f[i], f[i - 3] + abs(n1[i - 2] - n2[i]) + abs(n1[i - 1] - n2[i - 1]) + abs(n1[i] - n2[i - 2]));
	}

	printf("%lld\n", f[n]);
	return 0;
}

杂项

• 记得要开 $long long$ 。
• 这份代码十分暴力。