3

我需要一个特定的数据结构，但我不确定我应该使用什么。

我有一个矩阵 NxN。每个单元格都有一些整数值。对于矩阵中的任何矩形，我需要计算一个“价格”，这样：

price = sum( #value_of_field * #distance_from_target ) over cells in rectangle

距离是曼哈顿距离，目标可以是矩形中的任何单元格。矩阵是固定的（不变的）。

例子：

1 2
1 2

左上为 [0;0]，左下为 [0;1]，右上为 [1;0]，右下为 [1;1]

例如，给定矩形 [0;0] - [1;1]（整个矩阵）中的 [0;0]，价格将是：

price = 1 * 0        +      2 * 1       +    1 * 1         +        2 * 2    =  7
        price of           price of           
        [0;0] *            [1;0] *           .....                   ....
        distance           distance
        from [0;0]         from [0;0]

我应该如何解决这个问题？mxn 中的解决方案（其中 m，n 是矩形的尺寸）很容易，但速度很慢。如何加快速度（例如预先计算某些东西）？

4

1 回答 1

1

预先计算 Ai 和 Bi：

  • Ai = 第 i 行元素的总和
  • Bi = 第 i 列元素的总和

公式

这会给你答案。

时间复杂度是O(N)针对每个价格计算的。准备 Ai 和 Bi 的时间复杂度也是O(N)如此。

于 2013-05-28T07:23:00.217 回答