周长面积等问题

Published: by Creative Commons Licence

  • Tags:

周长问题(自创)

题意

设在某个数轴上有n条垂直数轴的柱子,第i条柱子的高度为$h_i$($h_i > 0$),位置为$x_i$($x_i$互不相同)。

现在我们希望加入一个水平的线,使得其连接两个柱子,与两个柱子以及数轴构成一个矩形,求矩形可能的最大周长。

题解

我们可以将柱子规约为二维向量,第i个柱子为$(x_i,y_i)$。现在我们希望找到$i\neq j$,使得下式最大化

首先我们将所有柱子按照$y$值进行从小到大排序,之后我们按序处理柱子。考虑现在处理第$j$个柱子,我们希望在已经处理过的柱子中找到一个柱子$i$,使得下式最大化:

由于绝对值非常烦人,但是绝对值拥有着最大化的语义,即 ,因此我们实际上要使下面公式最大化:

上面这个公式是非常容易求解的,只需要我们维护已经处理过的所有柱子的$y_i+x_i$的最大值以及$y_i-x_i$的最大值即可。

这个问题的总的时间复杂度为$O(n\log_2n)$。