[問題] ZJ-c223: Add All(變異版)(已解決)

看板 Prob_Solve
作者
時間
留言 5則留言,4人參與討論
推噓 1  ( 1推 0噓 4→ )
先感謝這兩天 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://www.ptt.cc/bbs/Prob_Solve/M.1559748493.A.B22.html
1FoToToT: ZJ的時間測量好像不是非常的stable 06/05 23:51
2Ffatcat8127: 感謝oToToT和cutecpu的回覆,晚點整理兩位大大的內容 06/06 17:34
3Fpttworld: 這題用getchar()勉強寫進1s內。 06/06 18:26
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 06/07/2019 16:55:57 ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 06/07/2019 18:22:36
4Ffirejox: getchar_unlocked 06/09 13:19
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 06/17/2019 02:43:46
5Ffatcat8127: 關於加速讀取和輸出的練習可以嘗試ZJ-e273 06/17 03:41