[POJ 2452]RMQ、二分枚举

【题目大意】给定一个长度为N的没有相同元素的序列,然后让你求一个连续子串A[I],A[I+1]....A[J]使得A[I]是这短子串中的最小值,A[J]是这段子串中的最大值,并使得它J-I的值最大。

【算法分析】我先假设确定了起点,然后考虑在O(lgN)的复杂度里找到对应的最长长度。对于这个问题,我们可以考虑先找出以I为起点的区间范围,即以A[I]为最小值的区间范围。找出这个范围以后,只需要再找出其中的最大值所在的位置,就已经找出了以I为起点对应的最长区间了。(因为这个数在可取值的范围里最大,所以不能再延伸区间了)。对于实现这个算法,我们很容易得到确定了起点的最小值单调递减,于是我们可以二分得到这个范围,复杂度O(lgN)。然后那个取最大值和最小值均可以用RMQ在O(1)的复杂度内搞出来。由于预处理RMQ复杂度也为O(NlgN),所以整个算法的复杂度是O(NlgN)。

【其它】1A,今天的第10题,刷完睡觉

6430690 edward2 2452 Accepted 12516K 766MS G++ 1971B 2010-02-10 01:08:32

【CODE】

#include

留下评论

您的电子邮箱地址不会被公开。