考察知识点:数学
经典的约瑟夫环问题,模拟即可,下面的代码提供了一种思路。
时间复杂度:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
void solve()
{
int n, k;
cin >> n >> k;
vi a(n);
for (int i = 0; i < n; i++)
a[i] = i + 1;
int cnt = n, x = 0, cur = 0;
while (cnt)
{
if (a[cur] != 0)
x++;
if (x == k)
{
cout << a[cur] << " ";
a[cur] = 0;
cnt--;
x = 0;
}
cur = (cur + 1) % n;
}
cout << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
也可以用循环链表模拟。