以最低成本找到建筑物的共同高度

Question

这是一些编程竞赛中的一个问题(我不确切知道它属于哪个编程竞赛,我在一年前看到它).问题如下:

有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).

我认为的蛮力方法如下:

无论常见的高度是多少,它都必须来自

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

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

是否可以更快地完成它？

Answer 1

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 座建筑物的建筑物的高度等于排序数组 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 个建筑物的建筑物等于排序数组 P 中第 i 个建筑物的高度的成本，即如果我们使建筑物 P(1) 的 Cost_of_decrease(i) ), 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) 栋建筑物的总成本为：

增加成本 (i) + 减少成本 (i)。

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

希望能帮助到你 ！