ABC330F Minimize Bounding Square 题解

· · 题解

Problem

二分是什么东西？不需要不需要。这里提供一个逆天的贪心做法。

首先是基本的贪心思想：争取把所有点都往“里”缩。

我们记 S 为能包围初始点的最小矩形。

如果 S 是长方形，那么我们一定要把它缩成正方形。具体来说，我们考虑一个贪心：将长方形上的两个短边（即我们要缩的边）中含点数较少的那个边往里缩，这样一定是不亏的。

因为 x 和 y 互不干扰，不会因为收缩了 x 就影响 y ，因此在都是让答案 -1 的情况下，我们一定会选择代价较小的边进行收缩。

如果每次收缩距离为 1 ，那面对 10^9 的值域就会无能为力。因此每次我们收缩到下一个有点的地方。可以用 \operatorname{map} 维护横坐标和纵坐标。

好的，现在我们已经把 S 缩成一个正方形了。接下来我们要把 S 变成一个更小的正方形。采取和上面类似的策略，我们选取代价最小的两条邻边然后往里缩。还是缩到第一个有点的位置。

于是一通贪下去这道题就做完了，只是代码量和常数略大。注意到每一次往里缩至少会使 S 的边界上增加一个点，因此这部分复杂度为 \mathcal{O}(n) 。最后时间复杂度的瓶颈在 \operatorname{map} 上。

Submission