最接近極限的那筆

我看了解題報告還是霧煞煞

我用了vector模擬

「人數過少的情況用dp做」

這行比較看不懂作法

有人可以幫忙解釋一下?

我看完這題的解題報告後也不是很懂版主的問題

我想加問: Try & Error 方式 是甚麼意思?

例外處理嗎??

Try & Error 就是根據錯誤反推出題者的意圖來修正程式碼，考試情況下是不會公開錯誤訊息，所以無法找出利用 Try & Error 來反推

這類問題的原型叫做『喬瑟夫問題』Josephus Problem，動態規劃的解法請參考維基的說明( https://en.wikipedia.org/wiki/Josephus_problem )

既然動態規劃這麼OP，為何不能用在這題呢？因為動態規劃只能解出最後一個存活者號碼，而非問題要求的殺完第K個人時活著的下一個號碼

偏偏用 vector 模擬移除被殺掉的人會出現 TLE 。這時請搜尋『 UVa1452- Jump 』題目要求輸出『最後活著的三個號碼』。

理解怎麼把動態規劃解法的最後一個存活者推導到最後活著三個人的方法( 解法很多就請大家自行搜尋 )，可以發現做法的時間成本和需要紀錄剩餘者的人數有關

追蹤最後活著的 K 個人時需要 KN 的時間找出這些號碼，K必然不可太大(N=2e6)。

回到我們的最終目標是『殺完第K個人時活著的下一個號碼』換句話說我們需要的資訊是最後活著 N-K+1  個人的情況下所有的號碼，並且當第 K 個人被殺時下一個活著的號碼

利用二分法找到第 K 個被殺掉的號碼後計算出『下一個』活著的號碼即可。

以上所有的推論都是建立在 K 不能太大的情況下，所以觀察最後一筆測資：200000 999997 199998，可以發現滿足解法的限制。

原文再吃掉

後來看懂『動態規劃』的推導之後就可以發現需要通過最後一筆測資只能用該方法

最後一筆測資的目的是要擋掉使用 vector 模擬移除的作法，使用動態規劃的時間只需 5 ms左右且不需要耗費過多的記憶體。

至於我前面說的動態規劃部分可以不用管 K 的大小，都可以用動態規劃解法

解法網路上應該可以GOOGLE的到，至於理解的方式請大家自行揣摩，畢竟這是動態規劃的難處。