UVa 1312球场(cricket field)
发布时间
阅读量:
阅读量
题意:
在一个尺寸为 W*H 的网格中分布着 n 棵树,目标是寻找面积最大的空置正方形。
分析:
树木的数量范围在 1 至 100 之间。
若采用遍历所有树木的方式,每次确定两个树木之间的上下边界,并从左至右枚举两个树木之间的左右边界,
则所需时间复杂度为 O(n^4),约需执行 1e8 次操作,这将导致超时问题。
那么,在从左到右进行枚举的过程中是否存在优化空间?
答案是肯定的。
当之前枚举的树木的 y 坐标不在当前所选两个树木的上下边界范围内时,其对后续 x 坐标的计算不会造成影响。
然而,若当前所选的 y 坐标位于这两个树木的上下边界范围内(不包含边界),则会对后续计算产生影响。
此时只需及时更新当前 y 坐标对应的树木 x 坐标的左端点即可。
通过上述方法可将时间复杂度降至 O(n^3)。
由于数据规模较小,该算法仍可在合理时间内完成执行。
代码:
#include<bits/stdc++.h>
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
using namespace std;
int len;
int xx, yy;
struct Point {
int x, y;
全部评论 (0)
还没有任何评论哟~
