周长面积等问题

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$,使得下式最大化

\[\min(y_i,y_j)+|x_i-y_i|\]

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

\[y_i+|x_i-x_j|\]

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

\[y_i+\max(x_i-x_j,x_j-x_i)=\max(y_i+x_i-x_j,y_i-x_i+x_j)\]

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

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