P1168 中位数 题解

KobeBeanBryantCox · 2024-08-08 14:26:12 · 题解

P1168 中位数 题解

题目传送门。

本题解用 5 种方法过这个题，讲述顺序由易到难。

本文最后会比较各个方法的用时、空间、码量和好写程度。

代码放在云剪贴板，链接在最后。

题意

给定一个长度为 N 的非负整数序列 A，对于前奇数项求中位数。

1. 暴力 vector

保证每次插入的时候原序列有序就行了。

所以用一个二分查找找到插入的位置插入就行了。

理论时间复杂度 O(n^2\log n)，但是常数极小，而且跑不满。

不保证加强数据以后能过。

2. 优先队列（堆）

维护两个堆：比当前中位数小的和比它大的。

插入，就与中位数比较，选择哪个插入；

输出，把中位数放入元素少的，把元素多的设置成中位数，循环操作。

由于不平衡的状态次数不多，理论时间复杂度 O(n\log n)。

3. 值域线段树

先离散化。

然后插入就直接插入；输出就在线段树上二分，找到中位数就行。

理论时间复杂度 O(n\log n)。

4. 分块

我这里的分块比这篇题解的分块好理解。

先离散化，对值域分块，维护每一块的和。

插入就直接插入，更新值域数组以及块和；

输出有点麻烦。

暴力算一个块内和的前缀和，二分查找中位数在哪一个块。

然后再暴力算这个块的前缀和，二分查找中位数在这个块的哪个位置。

块长取 \sqrt n，理论时间复杂度 O(n\times(\sqrt n+\log n))。

当然块长如果改一下还有可能更快，不过蒟蒻不会算块长。

5. 平衡树

这是平衡树模板题啊 QWQ。

我采用的是 FHQ-Treap。

理论时间复杂度 O(n\log n)。

代码 & 比较分析

代码放云剪贴板。

评测环境：

-std=c++17 -O2，开快读快输。

综上：优先队列最快，优先队列用空间少，暴力码量少，暴力最好写。

分块比平衡树快的原因应该是平衡树常数太大了。

后记

如果哪里有讲错的欢迎提出，如果讲得不清楚欢迎提问。

麻烦点个赞，点个关注。

说句闲话：研究珂学的最好方法是：

A 了这道题。

祝你们成功（滑稽。