bzoj 1052: [HAOI2007]覆盖问题 二分

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1052


对于这样的问题,直接就能想到二分

这个做法我之前以为会TLE,没想到居然跑的很快..

 

我们发现,对于三个正方形,一定至少有一个是放在角落的

先二分边长,再尝试着把正方形分别放到四个角落

然后暴力地去覆盖点,对于两个正方形来说也一定至少有一个在角落,所以接着暴力覆盖

剩下1个正方形时,判断一下能不能完全覆盖就好

 

发表评论