O(n.logn)中的Josephus Permutation(删除顺序)

Question

有没有办法打印出O(n.logn(中Josephus问题的删除顺序？

示例

人数为n = 7，人数为跳过k = 3。淘汰顺序为：

3, 6, 2, 7, 5, 1, 4

Answer 1

有一种方法使用有序集

(https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/)：

• 初始化有序集V，并将范围[1，N]中的元素插入V中
• 初始化一个变量，比如pos为0，以存储已删除元素的索引
• 重复，直到V的大小大于1，然后执行以下步骤：
  • 将集合的大小存储在变量中，例如X
  • 将pos的值更新为(pos+K(%X
  • 打印V中pos指向的元素，然后将其擦除
  • 将pos更新为pos%V.size((
• 打印存储在集合V开头的最后一个元素

这是代码：

#include <iostream>
using namespace std;
// Header files, namespaces to use
// ordered set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set                          
tree<int, null_type, less<int>, rb_tree_tag, 
tree_order_statistics_node_update>
// Function to find the person who
// will get killed in the i'th step
void orderOfExecution(int N, int K)
{
// Create an ordered set
ordered_set V;
// Push elements in the range
// [1, N] in the set
for (int i = 1; i <= N; ++i)
V.insert(i);
// Stores the position to be removed
int pos = 0;
// Iterate until the size of the set
// is greater than 1
while (V.size() > 1) {
// Update the position
pos = (pos + K) % (int)V.size();
// Print the removed element
cout << *(V.find_by_order(pos)) << ' ';
// Erase it from the ordered set
V.erase(*(V.find_by_order(pos)));
// Update position
pos %= (int)V.size();
}
// Print the first element of the set
cout << *(V.find_by_order(0));
}
int main()
{
int N = 5, K = 2;
// Function Call
orderOfExecution(N, K);
return 0;
}

时间复杂性：O(N*log(N((

为了更好地理解，我建议查看此视频：

https://youtu.be/KnsDFCcBJbY

Answer 2

您可以构建能够解决这些类型操作的分段树

• M(p，v(：修改a[p]：=v
• S(l，r(：计算a[l]+a[l+1]+…+a[r]
• F(p，k(：求(x>=p(和S(1，x(>=的最小值(x(k

所有上述操作都可以在O(logn(时间中完成

使用上述算法，您可以在O(n log n(中获得相同的结果

/*
@Author: SPyofgame
@License: Free to use
*/
#include <iostream>
#include <vector>
using namespace std;
/// Segment Tree Data Structure
struct Segtree
{
int n;
vector<int> t;
/// O(n)
/// Construct Segment Tree
void init(int lim)
{
for (n = 1; n < lim; n <<= 1);
t.assign(n << 1, 0);
}
/// O(log n)
/// Modify: a[pos] := v
void modify(int pos, int v, int ct, int lt, int rt)
{
if (rt - lt == 1)
{
t[ct] = v;
return ;
}
int mt = (lt + rt) >> 1;
if (mt > pos)
modify(pos, v, ct * 2 + 1, lt, mt);
else 
modify(pos, v, ct * 2 + 2, mt, rt);
t[ct] = t[ct * 2 + 1] + t[ct * 2 + 2];
}
/// O(log n)
void modify(int pos, int v)
{
return modify(pos, v, 0, 0, n);
}

/// O(log n)
/// Query: Sigma(a[i] | l <= i <= r)
int query(int l, int r, int ct, int lt, int rt)
{
if (lt >= r || l >= rt) return 0;
if (lt >= l && r >= rt) return t[ct];
int mt = (lt + rt) >> 1;
int lv = query(l, r, ct * 2 + 1, lt, mt);
int rv = query(l, r, ct * 2 + 2, mt, rt);
return lv + rv;
}
/// O(log n)
int query(int l, int r)
{
return query(l, r + 1, 0, 0, n);
}
/// O(log n)
/// Search: Min(x | Query(1, x) >= k)
int search_for(int k, int ct, int lt, int rt)
{
if (k > t[ct]) return -1;
if (rt - lt == 1) return lt;
int mt = (lt + rt) >> 1;
int v = t[ct * 2 + 1];
int res = search_for(k - 0, ct * 2 + 1, lt, mt);
if (res == -1)
res = search_for(k - v, ct * 2 + 2, mt, rt);

return res;
}
/// O(log n)
int search_for(int k)
{
return search_for(k, 0, 0, n);
}
/// O(log n)
/// Search: Min(x | x >= pos & Query(1, x) >= k)
int search_for_at_least(int pos, int k)
{
return search_for(k + query(1, pos - 1), 0, 0, n);
}
};
int main()
{
// file("Test");
ios::sync_with_stdio(NULL);
cin.tie(NULL);
/// Input: Number of element and steps
int n, k;
cin >> n >> k;
Segtree T;
T.init(n + 1);
for (int x = 1; x <= n; ++x) /// O(n log n)
T.modify(x, 1);
int pos = 1;
for (int remain = n; remain >= 1; --remain) /// O(n log n)
{
/// Number of steps
int step = k + 1;

/// Move move (remain) times remain the same pos
step %= remain;
if (step == 0) step = remain; /// Current pos my not the result, therefore move more (remain) steps
/// The current segment is not the part we need to search
int right = T.query(pos, n);
if (step > right)
{
pos = 1; /// Set it back to first pos
step -= right; /// Number of step traveled
}
/// Search for real pos
pos = T.search_for_at_least(pos, step);
T.modify(pos, 0);
cout << pos << " ";
}
return 0;
}

您也可以使用迭代分段树

/*
@Author: SPyofgame
@License: Free to use
*/
#include <iostream>

using namespace std;

const int N = 1 << 18;
int T[N+N];
void init(int n)
{
for (int i = 0; i < n; ++i) T[i + N] = 1;
for (int i = N - 1; i > 0; --i) T[i] = T[i << 1] + T[i << 1 | 1];
}

int lower_bound(int x, int p = 1)
{
while (p < N) if (T[p <<= 1] < x) x -= T[p++];
return p - N;
}

void update(int p, int v)
{
for (T[p += N] = v; p > 1; p >>= 1) T[p >> 1] = T[p] + T[p ^ 1];
}

int main()
{
int n, k;
cin >> n >> k;

init(n);
for (int remain = n, pos = 0; remain > 0; --remain)
{
pos += remain + k;
pos %= remain;
int p = lower_bound(pos + 1);
cout << p + 1 << " ";
update(p, 0);
}

return 0;
}