关于第一条题解为什么能过这件事

P1168 中位数

Kindolph @ 2023-12-22 17:45:36

P1168 中位数 题目链接

如题。\ 代码见题解 @decoqwq所写 或见于他的博客

vector的insert复杂度理论为O(n)，所以这个程序的复杂度实际上是O(n²)。但是实测跑了好几遍后测出来insert的复杂度（全部从头部插入，即最差情况下）为O(n/150)（非标准写法），也就是这个程序的时间复杂度是O(n²/150)。最大能过到200000，300000就不行了，题目恰好100000，所以能AC。第一条题解算是卡常数的做法了（

by cosf @ 2023-12-22 17:53:47

有没有可能，vector 的 insert 复杂度理论为 O(1)。

by Hanx16Kira @ 2023-12-22 17:54:13

vector insert() 最劣复杂度 \mathcal O(n)，但是常数极小，有些时候你用这玩意代替 set 比 set 跑的还快。

by Eznibuil @ 2023-12-22 17:57:21

听说过 flat_set 吗（

by qweradf @ 2023-12-22 18:30:56

@cosf 没有

by LinkWish @ 2023-12-22 18:54:41

@cosf 这玩意 O(1) 我要 set 干嘛

by wanggiaoxing @ 2023-12-22 19:37:21

@cosf 幽默

by lyht @ 2023-12-25 14:36:52

你要永远相信维克托

|