#创作计划# 猎奇
2025-09-07 14:43:51
发布于:广东
在“忠诚”这题中,我使用了乱搞解法,因为数据水通过了。
做法如下:
- 将 数组从大到小排序,并且记录每个数原来的下标。
- 查询时,将 数组从头到尾遍历一遍,找到第一个原来的下标在询问区间内的数,并输出它。
这么猎奇的做法为什么能过呢?原来它在随机数据(,查询区间的左、右端点均随机生成)下,时间复杂度期望 !接下来,我要证明这个结论:
由于随机生成,所以排序后原来的下标也是随机的。这就相当于在数组中随机撒点,看看哪个点最先落在区间上。显然,如果长度为 ,每次撒点撒中的概率为 ,而有点撒中的期望撒点次数为 。
那 为多少呢?显然它由区间的左右端点决定。注意到区间左右端点是随机的,所以 的概率约为 , 的概率为 , 的概率为 ,......, 的概率为 。
所以,整体的期望如下:
所以时间复杂度为 。
hack 这个算法的做法也挺简单的,一种做法如下:
将第 次询问的区间设置成 即可。
显然无论 数组长什么样,这些查询会让该算法分别撒点 次, 次, 次,......, 次,时间复杂度退化为 。
全部评论 9
当然,你这里计算时间复杂度时, 可以近似的看成是 ,再近似成
2025-09-13 来自 上海
0是的,但是我感觉 是约等于不严谨,就写了个一定比他大的式子
2025-09-13 来自 广东
0我这种方法就是拿调和级数是发散的的那个证明改了一下,确定了它的上界
2025-09-14 来自 广东
0考古,其实ln 的
2025-09-30 来自 上海
0
真棒
2025-09-07 来自 广东
0d
2025-09-07 来自 广东
0n
2n−1
×
2
n
+
n
2n−2
×
3
n
+...+
n
21
×
n
n
)2025-09-04 来自 陕西
0zc
2025-09-02 来自 广东
0d
2025-09-02 来自 广东
0d
2025-09-02 来自 广东
0此时在由乃救爷爷中亦有记载
2025-09-02 来自 广东
0d
2025-09-02 来自 广东
0

































有帮助,赞一个