[问题] ZJ-c223: Add All(变异版)(已解决)

楼主: fatcat8127 (胖胖猫)   2019-06-05 23:28:09
先感谢这两天 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 的主因还是读取方式,排序方式不是决定的关键。
如果大家有其他想法欢迎在下面留言,我晚点也会一并整理到内文中。
作者: oToToT (屁孩)   2019-06-05 23:51:00
ZJ的时间测量好像不是非常的stable
楼主: fatcat8127 (胖胖猫)   2019-06-06 17:34:00
感谢oToToT和cutecpu的回复,晚点整理两位大大的内容
作者: pttworld (批踢踢世界)   2019-06-06 18:26:00
这题用getchar()勉强写进1s内。
作者: firejox (Tangent)   2019-06-09 13:19:00
getchar_unlocked
楼主: fatcat8127 (胖胖猫)   2019-06-17 03:41:00
关于加速读取和输出的练习可以尝试ZJ-e273

Links booklink

Contact Us: admin [ a t ] ucptt.com