社区讨论

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

KKindolph
P1168中位数参与者 7已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lqgg5hlv
此快照首次捕获于
2023/12/22 17:46
2 年前
此快照最后确认于
2023/12/22 20:17
2 年前
查看原帖
P1168 中位数 题目链接
如题。
代码见题解 @decoqwq所写 或见于他的博客
vector的insert复杂度理论为O(n)，所以这个程序的复杂度实际上是O(n²)。但是实测跑了好几遍后测出来insert的复杂度（全部从头部插入，即最差情况下）为O(n/150)（非标准写法），也就是这个程序的时间复杂度是O(n²/150)。最大能过到200000，300000就不行了，题目恰好100000，所以能AC。第一条题解算是卡常数的做法了（

回复

共 6 条回复，欢迎继续交流。

正在加载回复...