約瑟夫問題是有兩千年歷史的經典: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 帳號,註冊只要一分鐘。