先感谢这两天 oToToT 和 cutecpu 的指导和讨论。
概括这题的核心要求:O(1)的操作和CountSort/Radix-Sort
是Uva-10954的加强版,原版的作法可以用 PriorityQueue 完成。
两题的差异在于 N=5e3 和 N=1e6 的量级,导致 PriorityQueue 的 log(N)作法会TLE。
而观察过程可以发现一个有趣的规律:
每次合并数列中最小的两个数字,合并后的这个数值是递增的(废话)。
但原版的作法是放回 PriorityQueue,但这样就会浪费递增这个性质,于是改良版就是
把合并后的数字用一个 Queue 存起来,每次放回数列的成本就降为O(1)。
取最小值时则只要考虑原本数列和现在这个 Queue 最前面的数字即可,所以也是O(1)。
详细的作法请参考inversion文章:https://pse.is/EF4H5
但即便达成上述的要求后还是可能会在最后一笔测资吃TLE,这里就要谈到加速读取。
一般加速读取会谈到 cin/cout 和 scanf()/printf() 的说明
可以参考这篇:https://pse.is/HMHLT。
我自己用getchar()做加速读取还是不够的。
但这篇的测资输入最大会 > 50M,以上的作法仍是不够的,因为IO次数还是太多。
于是我们便需要更底层的输入函数:fread() 或者是 fgets()
fread()版本(oToToT撰写):https://pastebin.com/gdbX9QxX
===
以下是fread()读取相关的说明文章,文章解释得很仔细就不多说仅附上网址
https://zhuanlan.zhihu.com/p/55304700
===
fgets()版本(cutecpu撰写):https://ideone.com/usX8gE
越底层的函数需要越清楚停止条件和读入缓冲区的大小,这边我举fgets()为例,
题目的第二行最多会有1e6个数字,每个数字不超过1e6(以字串来看长度不超过7),
且数字间用空白隔开,所以缓冲区的大小是1<<23( 7e6 ),停止条件是'\n'。
附上两个函数的使用方式和差异:https://pse.is/HKWJY
以及上述读取函数的时间比较:https://pse.is/J2A5N
最后排序的部分:假若采用CountSort约 0.4s 而呼叫内建的Qsort是 0.7s。
结论来说 TLE 的主因还是读取方式,排序方式不是决定的关键。
如果大家有其他想法欢迎在下面留言,我晚点也会一并整理到内文中。