語法書 / AA 競程語法書 下冊 / 第十六單元 / 每輪減半的威力:約瑟夫問題 1

16.5 每輪減半的威力:約瑟夫問題 1

約瑟夫問題是有兩千年歷史的經典:n 位小朋友(編號 1 到 n)圍成一圈,從編號 1 開始每隔一位移除一人(跳過一位、移除下一位),移除後從下一位繼續,直到所有人出局。本站題目〈約瑟夫問題 1〉(n \le 2 \times 10^5)要你輸出完整的移除順序。

最直覺的模擬:把大家放進 vector,游標繞圈走,輪到誰就 erase 誰。正確——但 10.5 警告過:erase 一次要搬動後面整段元素,O(n);移除 n 個人就是 O(n^2)。n = 2 \times 10^5 代進去約 10^{10} 量級——本站這題時限 0.5 秒,這個寫法實測要跑約 0.9 秒,穩穩 TLE。

登入後即可閱讀完整內容

語法書免費開放給所有 AACPOJ 帳號,註冊只要一分鐘。