P2218 题解

前言

题目传送门！

更好的阅读体验？

二分答案套搜索。

思路

答案显然具有单调性，于是可以二分答案。

问题是如何实现 \(\operatorname{check}(k)\) 函数（\(k\) 指薄膜边长）。

其实很简单：用 dfs 即可。

每次 dfs 时记录下当前是第几个薄膜。dfs 时，如果 \(\max\big(\small(\max x_i) - (\min x_i), (\max y_i) - (\min y_i)\big)\small \le k\)，说明 \(k\) 是可行解。

bool dfs(int c)
{
	int minx = inf, maxx = -inf, miny = inf, maxy = -inf;
	for (int i = 1; i <= n; i++)
		if (!flag[i])
			minx = min(minx, x[i]), maxx = max(maxx, x[i]), miny = min(miny, y[i]), maxy = max(maxy, y[i]);
	if (max(maxx - minx, maxy - miny) <= k) return true; //可以安装完
	if (c == 3) return false;
        //write other code here
}

覆盖时，考虑薄膜左上角与右下角的位置。看起来有很多情况，其实很少。

假设点分布的很不均匀，然后我们在中间的部分放一个薄膜。

这时，你会发现，边角上的点仍然要处理。这样，你不得不再花费薄膜在边角上放置，非常浪费。

因此，最好的方法就是全部贴着角放。

所以，左上角 \((x1, y1)\) 以及右下角 \((x2, y2)\)，一共只有四种可能。

横坐标两种可能：\(\begin{cases}x1 = (\min x_i) \\x2 = (\min x_i) + k\end{cases}\ \ \begin{cases}x1 = (\max x_i) - k \\x2 = (\max x_i)\end{cases}\)

同理，纵坐标有两种可能：\(\begin{cases}y1 = (\min y_i) \\y2 = (\min y_i) + k\end{cases}\ \ \begin{cases}y1 = (\max y_i) - k \\y2 = (\max y_i)\end{cases}\)

两两搭配就是四种了。具体可以见代码。

int dict[4][4]; //自己对比一下，依次指 x1, x2, y1, y2
dict[0][0] = minx, dict[0][1] = minx + k, dict[0][2] = miny, dict[0][3] = miny + k;
dict[1][0] = minx, dict[1][1] = minx + k, dict[1][2] = maxy - k, dict[1][3] = maxy;
dict[2][0] = maxx - k, dict[2][1] = maxx, dict[2][2] = miny, dict[2][3] = miny + k;
dict[3][0] = maxx - k, dict[3][1] = maxx, dict[3][2] = maxy - k, dict[3][3] = maxy;

依次枚举这四种情况，覆盖时暴力看能否盖住即可。

搜完后记得回溯。

for (int j = 0; j < 4; j++)
{
	int x1 = dict[j][0], x2 = dict[j][1], y1 = dict[j][2], y2 = dict[j][3];
	for (int i = 1; i <= n; i++) //覆盖
		if (!flag[i])
			if (x1 <= x[i] && x[i] <= x2 && y1 <= y[i] && y[i] <= y2)
				flag[i] = c;
	if (dfs(c + 1)) return true;
	for (int i = 1; i <= n; i++) //回溯
		if (flag[i] == c)
			flag[i] = 0;
}

坑点

1. 数组要清空！

2. 正如这篇题解所说，大部分变量都需要定义在函数内！
   比如本代码的 dict 数组，就一定要定义在 dfs 里，很诡异。

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20005, inf = 2147483647;
int x[N], y[N], flag[N]; //flag:是否已经被覆盖了
int k, n;
inline bool dfs(int c)
{
	int minx = inf, maxx = -inf, miny = inf, maxy = -inf;
	for (int i = 1; i <= n; i++)
		if (!flag[i])
			minx = min(minx, x[i]), maxx = max(maxx, x[i]), miny = min(miny, y[i]), maxy = max(maxy, y[i]);
	if (max(maxx - minx, maxy - miny) <= k) return true; //可以安装完
	if (c == 3) return false;
	int dict[4][4]; //自己对比一下，依次指 x1, x2, y1, y2
	dict[0][0] = minx, dict[0][1] = minx + k, dict[0][2] = miny, dict[0][3] = miny + k;
	dict[1][0] = minx, dict[1][1] = minx + k, dict[1][2] = maxy - k, dict[1][3] = maxy;
	dict[2][0] = maxx - k, dict[2][1] = maxx, dict[2][2] = miny, dict[2][3] = miny + k;
	dict[3][0] = maxx - k, dict[3][1] = maxx, dict[3][2] = maxy - k, dict[3][3] = maxy;
	for (int j = 0; j < 4; j++)
	{
		int x1 = dict[j][0], x2 = dict[j][1], y1 = dict[j][2], y2 = dict[j][3];
		for (int i = 1; i <= n; i++) //覆盖
			if (!flag[i])
				if (x1 <= x[i] && x[i] <= x2 && y1 <= y[i] && y[i] <= y2)
					flag[i] = c;
		if (dfs(c + 1)) return true;
		for (int i = 1; i <= n; i++) //回溯
			if (flag[i] == c)
				flag[i] = 0;
	}
	return false;
}
bool chk(int oh)
{
	k = oh;
	for (int i = 1; i <= n; i++) flag[i] = 0;
	return dfs(1);
}
int FIND(LL l, LL r)
{
	while (l < r) //FFFF【T】TTT
	{
		LL mid = (l + r) >> 1;
		if (chk(mid)) r = mid;
		else l = mid + 1;
	}
	return r;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
	cout << FIND(0, 2e9);
	return 0;
}

希望能帮助到大家！