计算最多包含 K 个（随机放置）的 NxN 矩阵中最大正方形的面积

Question

我有一个作业围绕着寻找最大正方形的面积，该正方形最多包含 NxN 矩阵中的 K 个（其余为零，N <= 2000）。 W 个 1 随机分布在矩阵上（因此暗示 K <= W）。我已经使用二进制搜索方法解决了它 - 关键是作业还告诉我在不到 2 秒的计算时间内解决问题，而我的速度不够快。

我试过的：正方形大小的二进制搜索算法，从下限 1 和上限 N-1 开始（最大区域为 N*N 是微不足道的，因为它仅在 K>=W 时发生）。当可以找到一个包含最多 K 个方块的方块大小为 (upper + lower)/2 时，它会将边界向上移动，否则向下移动 - 这个测试函数可能是导致程序运行 for太长了，因为在最坏的情况下它仍然需要 O(N²) 时间来检查一个正方形大小。遗憾的是，我对 binary/n-ary 搜索还很陌生，没有真正的方法来加快搜索速度。我想知道 ternary/n-ary 搜索是否有帮助。我也读过有关并行二进制搜索的内容，但我不确定如何实现它。非常感谢任何帮助。

遗憾的是我现在无法提供代码，因为它在我办公室的计算机上，但我正在寻找关于如何解决问题的更一般的想法，而不是任何具体的实现。

Answer 1

是的，来自在线评审系统 (domjudge)。我可能应该提到它应该在 2 秒内计算 20 个测试用例，因此为什么 2 秒可能不够。

至于代码，遗憾的是我目前无法提供。谢谢您的回答！

Answer 2

正如评论中所指出的，除非我们知道在线法官使用什么硬件，否则我们无法知道O(n^2 log n) 解决方案是否可以通过。一个 O(n^2 log n) 的解决方案可能应该能够通过，但你已经以一种使常数因子太大的方式编写它，例如通过以错误的方式迭代矩阵（这导致持续缓存未命中）。因此，在那种情况下，有必要查看您的代码以诊断任何性能错误。但也许法官在一些旧机器上， O(n^2 log n) 不应该通过。在这种情况下，您可以尝试 O(n^2) 解决方案。我将在下面描述一个。

对于 N×N 网格中的每个正方形 (i, j)，我们将计算最大的 M[i][j] 使得边长 M[i][j] 的正方形的右下角位于 ( i, j) 至多有 K 个。此外，我们将存储该方块中的个数 - 称之为 O[i][j]。整个问题实例的答案就是所有 (i, j) 中 M[i][j] 的最大值。

要计算这些 M[i][j] 和 O[i][j] 值，我们使用以下算法：

// precompute row and column partial sums
int bestM = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (i == 0 || j == 0) {
            // this case is trivial 
        } else {
            // use the values of M[i-1][j-1] and O[i-1][j-1] to compute M[i][j] and O[i][j]
        }
        bestM = std::max(bestM, M[i][j]);
    }
}
return bestM;

要从 M[i-1][j-1] 和 O[i-1][j-1] 计算 M[i][j] 和 O[i][j]，我们按如下步骤进行：我们知道 M[i][j] 最多是 M[i-1][j-1] + 1（因为边长 M[i-1][j-1] + 2 且右下角位于 (i, j) 的正方形将严格包含边长 M[i-1][j-1] + 1 且右下角位于 (i-1, j-1) 的正方形), 但众所周知那个正方形太大了)。所以我们有一个内部循环：

int o = /* number of ones in square of side length M[i-1][j-1] + 1 with lower right corner at (i, j) */;
for (int k = M[i-1][j-1] + 1; k >= 0; k--) {
    if (o <= K) {
        O[i][j] = o;
        M[i][j] = k;
        break;
    } else {
        // reduce o to be the number of ones in square of side length k-1 with lower right corner at (i, j)
    }
}

为了有效地计算 o，我们观察到边长 M[i-1][j-1] + 1 的平方与右下角在 (i, j) 处只是以下的不相交并集：

右下角在(i-1,j-1)的边长M[i-1][j-1]的平方，
一个L-shape由正方形的下边和右边组成，顶点在(i, j)

所以o的初始值就是区域1的个数O[i-1][j-1]和区域2的个数之和，我们可以得到后者如果我们预先计算了每一行和每一列的部分和，则为常数时间，如第一个伪代码块所示。同理，内循环每次o需要减去的时候，我们只需要减去一个L-shape中找到的个数，也就是边长的平方的上边和左边k，我们同样可以使用部分和来做。

总的运行时间是 O(N^2)，尽管有 3 个嵌套循环，因为当前正在评估的正方形的 upper-left 角永远不会向后移动，因此总量沿着正方形的每个对角线在内部循环中花费的时间与该对角线的大小成线性关系，这意味着总体运行时间与正方形总数成线性关系。

计算最多包含 K 个（随机放置）的 NxN 矩阵中最大正方形的面积

Evaluating the area of the largest square in a NxN-matrix that encompasses at most K ones (which are randomly placed)

c++

binary

search

matrix

square