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

这是一些编程竞赛的一个问题(我不确切知道它属于哪个编程竞赛，我在一年前见过)。问题如下:

有N座建筑物，每座都有自己的高度(不一定是唯一的)

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

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

允许的操作是:

我们可以为建筑物增加一些高度。

我们可以从建筑物中移除一些高度。

与每座建筑物相关的成本是要删除/增加单位高度。假设c(i)是为建筑物移除/增加单位高度的成本。各自的费用如下:

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

假设我们有足够的高度(单位)，我们必须找到使所有建筑物都具有相同高度所需的最低成本。

输入:
第一行将指定N个建筑物数。 (1 输入的第二行将用于建筑物的高度。

{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)中的答案。

有可能做得更快吗？

最佳答案

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

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

步骤1:根据各个建筑物的高度，以降序对建筑物进行排序。将该布置称为P.即P(1)是最大建筑物的高度，而P(n)是最小建筑物的高度。这需要O(n log n)。

步骤2:将建筑物的所有高度相加。令S表示该和。此步骤需要O(n)时间。

步骤3:如果我们使所有高度小于ith建筑物的建筑物的高度等于排序建筑物P中第ith建筑物的高度，则让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)表示成本，如果我们使所有高度大于ith建筑物的建筑物等于SORTED ARRAY P中第ith建筑物的高度，即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)。

一旦我们在所有建筑物中都拥有了这一点，只需检查成本最小的那一个，这就是答案。

希望能帮助到你 !

关于algorithm - 以最低的成本找到建筑物的共同高度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12559882/