# 麦田选址：题解

## 解法比较

出题人解法枚举障碍点与田地边界给出的两条水平支撑线，在这个条带内按横坐标扫描阻挡点，取相邻阻挡之间最大的正方形边长。最优空正方形可移动或扩张，直到受到边界或障碍限制，因此这些候选条带足够；边界接触的判定按题意处理。

Codex（GPT-6）的实现枚举竖直支撑线并扫描纵向间隙。交换横纵坐标即可得到上述水平扫描，同一支撑线证明适用于两种方向。障碍数为 $k$ 时，两者均为 $O(k^3)$ 时间、$O(k)$ 空间。

## 枚举左右边界

网格很大，但建筑数量很少。把建筑的列坐标与虚拟边界 $0,m+1$ 合并、排序并去重，得到候选边界集合。枚举其中两个数 $l<r$ ，考虑列号严格位于两者之间的条带，宽度为 $w=r-l-1$ .

只取位于该条带内部的建筑，按行坐标排序，并在两端补上 $0,n+1$ .任意相邻行坐标 $a,b$ 之间没有条带内的建筑，因此形成高 $h=b-a-1$ 、宽 $w$ 的空矩形，可放入边长 $\min(h,w)$ 的正方形。

预先将全部建筑按行排序；枚举一对列边界后，只需顺序扫描并过滤，无需重新排序。重复建筑只会产生空的间隙，不影响最大答案。

## 正确性

算法考察的每个空矩形都没有建筑，取其中较短边长的正方形一定合法。

反过来，考虑任意合法正方形。保持其行范围不变，尽量向左右扩展成空矩形，直到网格边界或该行范围内某个建筑将扩展阻挡。因此左右外侧边界都属于枚举的候选集合。对这一对边界扫描建筑时，必有一个相邻建筑行之间的空隙包含原正方形的全部行；条带宽度和该空隙高度都至少为原正方形边长。算法必然得到不小于它的答案。结合可行性，最终答案最优。

## 复杂度

候选列边界至多 $k+2$ 个，每对边界扫描 $k$ 个建筑。时间为 $O((k+1)^3)$ ，空间为 $O(k+1)$ ；这一写法也包含 $k=0$ 的情形。网格尺寸只影响坐标和答案，不需要建立 $n\times m$ 数组。