n+lognlogV查找最大值

来自Blogewoosh #6

啃了一下,写个翻译吧。

问题:你有一个数组,你不知道每个元素的大小,但是能够提出询问:a[x]是否>=v?你需要找出这个数组的最大值,只能询问n + lognlogV次。

我们首先随机一个排列,按照这个顺序来询问。

记录一个前缀最大值。如果当前值大于前缀最大值,就暴力二分求它的值。否则跳过。

由于随机序列的最长上升子序列期望长度是logn的,而前缀上升子序列 <= 最长上升子序列,所以期望长度不会超过logn。也就是只有logn个位置需要二分。

期望询问n + lognlogV次。

可以用于优化DP等......

原文地址:https://www.cnblogs.com/huyufeifei/p/10616943.html