有N座建筑物,每座建筑物都有自己的高度(不一定唯一)。
{h1,h2,h3,...,hn}
我们需要将所有建筑物的高度都设置为相同的值h。
允许的操作如下:
- 我们可以向建筑物添加一定的高度。
- 我们可以从建筑物中减少一定的高度。
每个建筑物增加或减少单位高度都会带来相应的成本。设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) 的时间内计算出答案。
是否可能更快地完成?
O(n^2)
方法。提供一个样例输入和输出也会改善问题。 - amit