Advertisement

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)

还没有任何评论哟~