尚未解答計算數學 Problem Solving- ZJ-c223: Add All(變異版)
計算數學 Problem Solving- ZJ-c223: Add All(變異版)
先感謝這兩天 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 的主因還是讀取方式，排序方式不是決定的關鍵。
如果大家有其他想法歡迎在下面留言，我晚點也會一並整理到內文中。
--
0個答案
計算數學 Problem Solving- ZJ-c223: Add All(變異版)
