5

这是某个编程竞赛的一个问题（我不知道它到底属于哪个编程竞赛，我在一年前看到过）。问题如下：

有 N 个建筑物，每个建筑物都有自己的高度（不一定是唯一的）

{h1,h2,h3,...,hn}

我们必须让所有相同高度的建筑物都说h。

允许的操作是：

  1. 我们可以给建筑物增加一些高度。
  2. 我们可以从建筑物中移除一些高度。

移除/添加单位高度需要与每栋建筑物相关的成本。假设 c(i) 是为建筑物移除/增加单位高度的成本。相应的费用如下：

{c1,c2,c3,...,cn}

假设我们有足够的可用高度（单位），我们必须找到使所有建筑物具有相同高度所需的最小成本。

输入：第一行将指定 N 个建筑物的数量。（1<=N<=100000）。第二行输入将是建筑物的高度。

{h1,h2,h3,...,hn}

第三行输入将给出成本数组

 {c1,c2,c3.....,cn}

输出

输出将只是所需的最低成本。

样本输入：

3

2 1 3

10 1000 1

样本输出

12

解释：将所有高度为 1 的建筑物制作成 10*(2-1) + 1000*(1-1) + 1*(3-1) 即 12。

我知道蛮力方法是O（n ^ 2）。

我认为的蛮力方法如下：

无论常见的高度 h 是什么，它都必须从

 {h1,h2,h3,....,hn}

即 h 必须等于任何 h(i) 。现在检查每个 h(i) 我可以计算 O(n^2) 中的答案。

有可能做得更快吗？

4

2 回答 2

2

O(n log(n)) 解决方案：

令 h(i) 表示第 i 个建筑物的高度，让 c(i) 表示第 i 个建筑物的成本。

  1. Step-1：根据各个建筑物的高度，按降序对建筑物进行排序。让这种安排称为 P。即 P(1) 是最大建筑物的高度，P(n) 是最小建筑物的高度。这需要 O(n log n)。
  2. 第 2 步：将建筑物的所有高度相加。让 S 表示这个总和。这一步需要 O(n) 时间。
  3. 步骤 3：如果我们使所有高度小于第 i 个建筑物的建筑物的高度等于 SORTED ARRAY P 中第 i 个建筑物的高度，则让 Cost_of_Increase(i) 表示成本，即如果我们使 Cost_of_Increase(i)建筑物 P(i-1), P(i-2), ... P(n) 等于第 P(i) 个建筑物的高度。

现在使用这个递归：

Cost_of_Increase(i) = Cost_of_Increase(i-1) + ( h(i)-h(i-1) )*( 第 P(i-1) 个建筑物到第 P(n) 个建筑物的成本总和)

注意在上面的递归中，i和i-1的顺序是按照P的顺序，即排序的顺序。

现在让 Cost_of_decrease(i) 表示如果我们使所有高度大于第 i 个建筑物的建筑物等于 SORTED ARRAY P 中第 i 个建筑物的高度的成本，即 Cost_of_decrease(i) 如果我们使建筑物 P(1 ), P(2), ... P(i-2), P(i-1) 等于第 P(i) 个建筑物的高度。

为此，请使用此递归：

Cost_of_decrease(i) = Cost_of_decrease(i+1) + ( h(i+1)-h(i) )*( 第 P(1) 个建筑物到第 P(i-1) 个建筑物的成本总和)

因此，使所有建筑物的高度等于 P(i) th 建筑物的总成本为：

Cost_of_Increase(i) + Cost_of_decrease(i)。

一旦我们对所有建筑物都有了这个，只需检查哪个成本最小，这就是答案。

希望能帮助到你 ！

于 2012-09-24T07:09:59.203 回答
1

算法结束后对所有建筑物的高度进行三元搜索或使用爬山算法。对于每个高度，您可以以线性时间计算成本，因此总体复杂度将为 O(N * log(H))，其中 H 是可能产生的最大高度。

编辑：这是一个应该为你工作的伪代码片段（这是类似爬山的方法）

  typedef long long ll;
  ll get_cost(int h) {
    if (h < 0 || h > MAX_HEIGHT) {
      return MAX_VAL; // some unreachable positive value
    }
    ...
  }


  int main() {
    ...
    int current = 0;
    int leftp, rightp;
    ll cv, lv, rv;
    ll step = SOME_BIG_ENOUGH_VALUE;
    while (step > 0) {
      leftp = current - step;
      rightp = current + step;
      cv = get_cost(current);
      lv = get_cost(leftp);
      rv = get_cost(rightp);
      if (cv <= rv && cv <= lv) {
        step /= 2;
      } else if (lv < rv) {
        current = leftp;
      } else {
        current = rightp;
      }
    }
    ...
  }
于 2012-09-24T06:58:16.610 回答