1 条题解
-
0
题目分析
当遗址中只有一块危险区域时,问题可以较容易地解决。最优的正方形发掘区一定贴着这块危险区的某一个角落摆放(例如位于其“左下角”)。通过枚举发掘区的四种放置方式(危险区的左上、右上、左下、右下),并计算出在这些放置方式下的最大可能边长。
当危险区数量大于 1 时,考虑一种暴力做法:枚举所有可能的发掘区位置和边长,检查每个候选正方形区域内是否存在危险点。
考虑优化,可以发现,危险区域非常少,最多仅为 100 个。因此就想:是否可以通过枚举危险区域来枚举正方形。
很明显的,正方形的上、下、左、右界限,会被危险区域或者边界所限制。而此时它的边长,就为上下界距离、左右界距离中更小的那一个。而代表上下界的树一定在两棵左右界树之间。因此,基本的枚举思路,就是将危险区域从左到右进行排序,接着枚举所有可能的左右界。在每一次从左界开始往右枚举右界时,就可以顺便求出中间的上下界。具体来说,从左界那个危险区域所在行向上找到的第一个在左右界中的危险区域是上界,下届同理。
有一些特殊情况
- 相邻两/三界为边界:可以证明,此时的最优正方形必有一个角是靠在墙上的。
- 左界/右界为墙:这种情况,我们只需要以上下顺序排序,并以枚举上下界的方式走一遍我们之前的枚举左右界的程序即可。
- 1
信息
- ID
- 143
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者