17.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。
換個角度看這個過程：一整輪繞下來，恰好每兩人移除一人。與其逐一 erase，不如整輪處理完再重建——掃過目前的隊伍，被跳過的收進新 vector、被移除的直接輸出，一輪只花「目前人數」的工：
- 第一輪 n 人、第二輪約 n/2 人、第三輪約 n/4 人……
- 總工作量 n + \dfrac{n}{2} + \dfrac{n}{4} + \cdots < 2n——想像一條長度 2 的線段：先走 1、再走 \dfrac{1}{2}、再走 \dfrac{1}{4}……永遠走不出去。每輪減半的總量，撐死是第一輪的兩倍。
所以整體是 O(n)。唯一要小心的細節：一輪結束時「下一位要不要被移除」得帶到下一輪——用一個旗標記住它。
¶完整程式碼
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> alive(n);
for (int i = 0; i < n; i++) alive[i] = i + 1;
bool removeNext = false; // 輪到的這位要不要被移除（跨輪保留）
bool first = true;
while (!alive.empty()) {
vector<int> next;
for (int i = 0; i < (int)alive.size(); i++) {
if (removeNext) {
if (!first) cout << ' ';
cout << alive[i]; // 被移除：直接輸出
first = false;
removeNext = false;
} else {
next.push_back(alive[i]); // 被跳過：留到下一輪
removeNext = true;
}
}
alive = next;
}
cout << '\n';
return 0;
}
執行結果（輸入 7）：
2 4 6 1 5 3 7本站實測 n = 2 \times 10^5：逐一 erase 版約 0.9 秒（TLE），每輪重建版約 0.02 秒。同樣是「照規則模擬」，操作的成本選對了，形狀就換掉了。
「每輪減半」這個節奏請先記在心裡——下一節它有個專屬的名字。