发现拥有最小成本的建筑物共同高度

Question

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

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

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

我们需要将所有建筑物的高度都设置为相同的值h。

允许的操作如下：

1. 我们可以向建筑物添加一定的高度。
2. 我们可以从建筑物中减少一定的高度。

每个建筑物增加或减少单位高度都会带来相应的成本。设c(i)是将建筑物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) 的时间内计算出答案。

是否可能更快地完成？

- Akashdeep Saluja

---

输入的大小是多少？您还应该详细说明您所考虑的O(n^2)方法。提供一个样例输入和输出也会改善问题。 - amit

修改了我的解决方案。看一下吧。希望能有所帮助！ - user1599964

Answer 1

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

令 h(i) 表示第 i 座大楼的高度，c(i) 表示第 i 座大楼的成本。

1. 步骤1：按照各自大楼高度的降序对大楼进行排序。将此排序称为 P。即 P(1) 是最高建筑物的高度，P(n) 是最小建筑物的高度。这需要 O(n log n) 的时间。
2. 步骤2：将所有大楼的高度相加。令 S 表示此总和。此步骤需要 O(n) 的时间。
3. 步骤3：令 Cost_of_Increase(i) 表示如果我们使所有高度小于第 i 座大楼的建筑物高度等于排序数组 P 中第 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 座建筑物的建筑物高度等于排序数组 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) 号建筑物的总成本为：

Cost_of_Increase(i) + Cost_of_decrease(i)。

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

希望对您有所帮助！

- user1599964

Answer 2

在算法结束后，对所有建筑物的高度进行三分查找或使用爬山算法。对于每个高度，您可以在线性时间内计算成本，因此总体复杂度将为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;
      }
    }
    ...
  }

- Ivaylo Strandjev

---

在你的伪代码中，例如：if(lv<rv)，你正在使current=leftp，因此你忽略了先前当前位置的整个右分区，可能存在某个解决方案在先前的当前位置和先前的rightp之间。 - Akashdeep Saluja

整个解决方案取决于函数图像看起来像一个抛物线，即具有单个局部极值点。我相信这在这个问题中是成立的。相信我，我已经用这种方法解决了许多问题，并且我相信我已经用类似的代码解决了这个特定的问题。 - Ivaylo Strandjev

好的，也许很多问题都可能会出现这种情况...但我只是想澄清一下，是否存在一种解决方案适用于我上述提出的情境，即你的解决方案是否存在任何可能失败的测试用例？ - Akashdeep Saluja

@AkashdeepSaluja 这个问题不是针对这个。但很容易想到一个例子，这种解决方案并不容易应用，因为有许多局部最小值。总的来说，这种方法帮助我解决了许多问题，并且通常比其他解决方案（例如用户1599964提出的解决方案）更快实现。别误会 - 他的解决方案很好，也是正确的，只是更难实现，因此更容易出错。 - Ivaylo Strandjev