題意#
此為「約瑟夫問題」的進階版。
\( n \) 個人圍成一圈，編號為 1 到 \( n \)。
規則改為：跳過 \( k \) 個人，然後淘汰下一個人（即每數到第 \( k+1 \) 個人進行淘汰）。
被淘汰者出局後，圈子縮小，由下一位繼續重新計算跳過 \( k \) 個人。
需要依序輸出被淘汰的人的編號。
思路#
若使用 Queue 或陣列直接模擬每次「跳過 \( k \) 個人」的過程，時間複雜度會過高導致 TLE。
為了高效處理，可使用 C++ 的 __gnu_pbds（Policy Based Data Structure）紅黑樹來加速模擬。
PBDS 提供的 tree 擁有以下關鍵特性：
find_by_order(k)：以 \(\mathcal{O}(\log N)\) 找出樹中「第 \( k \) 小」的元素。order_of_key(x)：查詢樹中「嚴格小於」\( x \) 的元素數量。
本題將使用 find_by_order。
首先將 1 到 \( n \) 插入 PBDS 紅黑樹中，並使用變數 now 記錄當前淘汰位置的「相對排名（0-based）」。
每次淘汰流程如下：
- 利用圓環的特性，下一次淘汰的位置排名為
(now + k) % 剩餘人數。 - 透過
find_by_order(now)取出該排名的編號並輸出，最後使用erase將其從樹中移除。 - 移除後，樹內剩餘元素的排名會自動遞補，因此
now自然指向下一個要開始計算的位置。
此方法每次尋找與刪除皆只需 \(\mathcal{O}(\log N)\)，整體時間複雜度為 \(\mathcal{O}(N \log N)\)。
程式碼#
#include <bits/stdc++.h>
// 引入 PBDS 所需的標頭檔
#include <bits/extc++.h>
using namespace std;
// 使用 pbds 的命名空間
using namespace __gnu_pbds;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// 宣告一個支援 O(log N) 查詢「第 K 大小」的紅黑樹
signed main() { WA();
int n, k; cin >> n >> k;
// 定義 pbds 的 tree 型別，這是一棵儲存 int 的紅黑樹
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;
// 最初將 1 到 n 依序插入紅黑樹中
for (int i = 1; i <= n; i++) t.insert(i);
// now 記錄目前淘汰的「相對排名（0-based）」
int now = 0;
// 持續執行直到所有人皆被淘汰
while (t.size()) {
// 取得跨越 k 人後目標的位置排名
now = (now+k)%t.size();
// 透過 find_by_order 取出該排名的元素
cout << *t.find_by_order(now) << ' ';
// 從樹中將該元素刪除
t.erase(t.find_by_order(now));
}
}
