这是某个编程竞赛的一个问题(我不知道它到底属于哪个编程竞赛,我在一年前看到过)。问题如下:
有 N 个建筑物,每个建筑物都有自己的高度(不一定是唯一的)
{h1,h2,h3,...,hn}
我们必须让所有相同高度的建筑物都说h。
允许的操作是:
- 我们可以给建筑物增加一些高度。
- 我们可以从建筑物中移除一些高度。
移除/添加单位高度需要与每栋建筑物相关的成本。假设 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) 中的答案。
有可能做得更快吗?