- 「模板」序列排序（标准版）
-
bfw LV 9 @ 2020-08-03 08:20:58
首先 \(\text{STL}\) 的各种 \(\text{sort}\) 不可否认是 \(\mathcal{O}(n \log n)\) 的，包括 \(\text{vector}\) 排序，\(\text{set}\) 排序，优先队列（堆）排序等。
本身 \(\text{STL sort}\) 就是正解的一种，为啥要卡？
实际上加强版就是某某排序的模板（看透不说透，懂），不过个人建议还是要用随机种子。
比方说给定 \(k,a_1\)，按照 \(a_i = (999983 \times a_{i-1} + 2333333)%k\) 的方式生成，然后 \(k \leq 10^5\)，可以含蓄一点的 ~
1 条评论
-
oistream (oistream) LV 8 MOD @ 2020-08-03 16:43:00
一句话概述：卡
sort()是基于对本题 目的 的考虑，但从造数据难度考虑，我还是决定不卡。
模板题的算法本身就是显而易见的，所以不妨说出来。
本题是快排、堆排等 \(O(n\log n)\) 排序算法的模板题，如果用
sort()轻易水过那反应不出来本题所要考察算法的真实难度，也达不到本题的真实目的。纯随机的数据显然
sort()是有优势的，我记得sort()内部好像对基本有序的数据有特判以及特殊处理，所以估计比较难卡。所以我也是觉得不如就造个随机数据算了 /
-
@ 2020-08-04 08:17:50
- 误解了，以为您在说
set，priority_queue的内部支持排序 sort这东西么，卡肯定是卡不掉的。- 什么叫 比较难卡 ，那叫 根本卡不掉 ，你无法否认这是一个正确且简洁的方式，只不过呢。。
- 误解了，以为您在说
-
@ 2020-08-04 16:09:50
@bfw: 卡，能卡掉，但问题是与此同时还会有一批写的正常的快排被卡掉 /
-
@ 2020-08-05 07:46:37
@oistream (oistream): 当然，不否认 \(n \leq 10^7\)
-
@ 2020-08-05 09:11:42
@bfw: 捕捉，然鹅是不是晚了...
-
- 1