3

您有一个n x n网格，其中有n行和n列。对于每一列j，您将获得一个数字 C j，对于每一行i您将获得一个数字 R i。您需要在网格上标记一些点，这样：

  • 每行标记点数最多为 R i；
  • 每列的标记点数最多为 C j；
  • 您标记满足最后两个约束的最大点数并返回此点数。

输入为：n（网格的维度）；R i的序列和 C j的序列。

例如在这个网格中，回报是 34 例子

在线性时间内找到一个算法：O( n ) 或 O( n log( n )) 并带有演示。我找到了 Max-Flow alg 的解决方案。但是复杂度太高了。

4

2 回答 2

1

提示

我建议按照从最大 Ri 到最小的顺序遍历行。

跟踪每列有多少个空格。空格数从给定的 Cj 值开始。

对于每一行，根据列中当前的空格数，在网格中标记尽可能多的点。确保首先将点放在空格数最多的列中。

于 2015-12-01T11:43:41.420 回答
0

@尼克拉斯B。使用增强的自平衡二叉搜索树，您可以在 O(Log n) 中将一个区间减 1，但是如何找到在 O(n) 的次要时间内不为零的元素数量？在这种情况下，例如输入4 3322 3322 3322 -> 2212 -> 1111 -> 0011 -> 0000 您取数字 3（行指示符的第一个元素）并将列的间隔 [0,2] 减 1，此成本为 O(Log n)，并且列指示符都是 > 0，但是当您到达 0011 时，您必须提醒 2 为零，因为如果您在行中有 3，如果您不想要一个负数，您只能减去 2。如果您说零的数量你只能取 n 的间隔 - 0 的数量。但是你如何在不是 O(n) 的复杂时间中管理这个问题？

于 2015-12-05T13:02:44.053 回答