先感谢这两天 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 的主因还是读取方式，排序方式不是决定的关键。 如果大家有其他想法欢迎在下面留言，我晚点也会一并整理到内文中。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.222.86.91 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1559748493.A.B22.html ※ 编辑: fatcat8127 (61.222.86.91 台湾), 06/07/2019 16:55:57 ※ 编辑: fatcat8127 (61.222.86.91 台湾), 06/07/2019 18:22:36 ※ 编辑: fatcat8127 (61.222.86.91 台湾), 06/17/2019 02:43:46