略譯

原題目連結

註冊 n 個發信器給你的系統，
每個發信器有一個 id 和一個間隔 t，
表示它每隔 t 秒發出一次訊息；
若是同一秒發出的訊息，以 id 小的先，
問你前 k 個訊息分別是誰發出的

題解

按照題意模擬，會是這樣：

枚舉 1 到 k 去找出第 k 個訊息是誰發出的

而第 i 個訊息，是由這 n 個發信器中，下次發訊時間最小者發出；

• 找出是誰發出訊號
• 決定它的下次發訊時間
• 找出下一個訊息
• …

暴力枚舉是誰的信號，
可以得到複雜度 kn 的做法

進一步優化

仔細觀察，這方法頻繁地在 n 個東西中，找出最小者輸出，讓它變大，
再找出最小者，…

這情況適合使用 heap 來尋找極小值，
於是得到了 k log n 的解決方法

實作提示

• 與其在 heap 中保存一堆數，造成交換時的麻煩，不如只保留 index
• 自刻 heap 的話，可以不需砍掉再加回去，改完時間直接對 head 做 down 整理即可