显然可以二分答案。
然而判定貌似更难?
设二分的答案是 mid。
考虑把箱子的长宽高全部减去 mid,所有盒子的后左下角三个坐标也都减去 mid。
这样子就只需要找一个没有被覆盖的点即可(它就是一个可行空间的后左下角)。
找没有被覆盖的点,显然可以扫描线。
(或许叫做扫描面?)
类比二维平面上的扫描线,我们可以把每个箱子的上下面作为边界,按照高度排序并扫描。
为了防止超出这个空间,我们可以一开始在维护的数据结构上全部加一,并把箱子的下表面加入扫描线(贡献为 −1)。
类似地,把箱子的上表面加入扫描线(贡献为 1),并在做完扫描线后把整个平面 −1。
然后考虑使用什么数据结构。
二维的话,可以试试树套树。
然鹅此题要支持矩形修改矩形查询最值,标记不好打,所以先枪毙。
考虑二维线段树,然鹅我不会(大雾)。
然后——n 才 1000,不如数组套线段树!
复杂度 O(n2log2n)。
以及注意计算几何题一些处理边界的 ±1 操作。
代码:
1 |
|