题解：AT_abc394_g [ABC394G] Dense Buildings

Judgelight · 2025-02-24 08:15:19 · 题解

传送门

考虑我们的走法一定是先下降到某一个楼层，然后一口气走过去，然后上升/下降到对应楼层。我们能够节约的部分只有一开始的下降过程，显然是下降得越少越好。所以我们的问题转化为找路径上的点的最大楼层最小值最大的路径，显然可以二分。二分之后转化为判定如果只能走最大楼层大于等于 k 的格子是否可达。

所以我们直接整体二分，用可撤销并查集维护连通性，复杂度为 O(n\log^2 n)。