题解 P2218【覆盖问题】 |
您所在的位置：网站首页 › 重叠等于未覆盖前提 › 题解 P2218【覆盖问题】 |
|
题解 P2218【覆盖问题】
张语诚ZYC 2023-05-01 20:31:17 Solution ## 前言 题目链接：[LINK](https://www.luogu.com.cn/problem/P2218) ~~萌新第一次交紫题题解~~，**如有错误之处还望大佬们指出**，这里会尽力让思路清晰。 ## 思路分析 首先我们要有一个**前置知识**：如果 $3$ 个较小正方形能够覆盖所有的点，那么较大的正方形就一定能够覆盖所有的点。（这很容易想到） 有了这个想法，我们再试想：**如果可以在一个可接受的复杂度内判断 $3$ 个当前大小正方形是否可以覆盖所有的点**，那么问题解决了！（至于怎么判断，后面会说） 令 $L$ 初始等于 $1$ ，当三个 $L$ 不能覆盖所有点时，令 $L$ 倍增，当三个 $L$ 可以覆盖所有点时，在当前 $L$ 与上一个 $L$ 内进行二分即可找到最小的 $L$ 值。二分与倍增的时间复杂度是非常优秀的。 现在重点讨论一下如何判断 $3$ 个当前大小正方形是否可以覆盖所有的点。 首先我们拿到一张图： [](https://pic2.imgdb.cn/item/644facc10d2dde577760a5f7.png) 现在我们找到上下左右最边界的 $4$ 个点（或者至少 $4$ 个，不过思路一样）： [](https://pic2.imgdb.cn/item/644fad610d2dde5777613dc4.png) 根据抽屉原理：一共有 $3$ 个正方形，共有 $4$ 个边界点，那么至少一个正方形要覆盖到黄色长方形的一个角上。 [](https://pic2.imgdb.cn/item/644fae460d2dde577762156a.png) 当然在哪个角上呢，我们并不知道，不过我们可以枚举每一个角，在每一个角的情况下分别考虑，看看是否有一个叫满足题意。 删去第一个正方形覆盖的点，至于第二个正方形，还是按照上述的思路重复做即可，也枚举边框举行四个角分别考虑。 删再去第二个点覆盖的点，判断第三个正方形能否能覆盖剩下的点即可（比较 $L$ 与剩下点边界正方形长宽的大小）。 至此，此题完成。 ## 后记 个人认为思路还是比较清晰的，代码就不贴了。 时间复杂度还是可以接受的，美中不足的是两次枚举四个角带一个 $16$ 的常数，并无较大影响，只要其他部分常数合理，就可以通过，如果有大佬有更好的解决方案，欢迎补充！ $$\texttt{The End by 张语诚ZYC}$$ |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |