我试图解决 SPOJ 中的KOPC12A问题。
问题链接：http ://www.spoj.com/problems/KOPC12A/
问题简述：
给定 n 栋建筑物，每栋建筑物的高度（砖块的数量）都不同，每栋建筑物都有添加或移除砖块的成本，找到使所有建筑物具有相同高度的最小成本。
在尝试解决这个问题后，虽然徒劳无功，但在根据高度对输入进行排序后，我遇到了一个使用三元搜索的解决方案。
我无法理解平衡建筑物高度的成本是如何变成单峰的（因为三元搜索只能应用于单峰函数）
这让我很难过，我无法继续前进。
对此的任何见解都非常感谢。
谢谢-
为了扩展sasha的评论，我们可以将函数的（强）单峰性定义f为条件
for all x < y < z, f(y) < max(f(x), f(z))
f以及作为条件的函数的（强）凸性
z - y y - x
for all x < y < z, f(y) < ----- f(x) + ----- f(z).
z - x z - x
设建筑物的高度为 ，h1, ..., hn单位改建费用为c1, ..., cn。f(h')使所有建筑物高度的成本h'是
sum i in {1, ..., n} of ci |h' - hi|.
现在这里是一系列命题，每个命题都有一个相当简单的证明，通过归纳得出f单峰的结论。
gwhereg(x) = |x|是凸的。h，对于所有凸函数g1，g2其中的函数g2(x) = g1(x - h)是凸的。c > 0，对于所有凸函数g1，g2其中的函数g2(x) = c g1(x)是凸的。g1和g2，其中的函数g3是g3(x) = g1(x) + g2(x)凸的。