Gravatar
lihaoze
积分:1315
提交:359 / 750

Pro1638  [IOI 1999]矩形地块(A Strip of Land)

这个题只是暴力枚举会超时,考虑优化。

对于行(y 轴),我们用双指针暴力枚举,时间复杂度是 $O(m)$ 。

对于列(x 轴),维护每一列(两个行指针间)的最值,然后用双指针枚举每一列,用单调队列维护两个列指针间的最值信息,求得矩形在 x 轴上的最长长度,然后乘以暴力枚举的 y 轴长度,时间复杂度是 $O(n)$。

最后,整体的时间复杂度是 $O(mn) \ (T(m, n) = 100mn = O(mn))$。


2022-10-19 21:29:33    
我有话要说
暂无人分享评论!