【题目来源】
洛谷：P1996 约瑟夫问题 - 洛谷
【题目描述】
\(n\) 个人围成一圈，从第一个人开始报数,数到 \(m\) 的人出列，再由下一个人重新从 \(1\) 开始报数，数到 \(m\) 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
【输入】
输入两个整数 \(n,m\)。
【输出】
输出一行 \(n\) 个整数，按顺序输出每个出圈人的编号。
【输入样例】
10 3
【输出样例】
3 6 9 2 7 1 8 5 10 4
【算法标签】
《洛谷 P1996 约瑟夫问题》 #模拟# #树状数组# #队列# #链表#
【代码详解】
// 使用树状数组实现
#include <bits/stdc++.h>
using namespace std;const int N = 105; // 最大人数int n, m; // n: 总人数, m: 报数间隔
int tr[N]; // 树状数组，用于标记人员是否在场（1=在场，0=已出列）/*** 计算lowbit：获取x的最低位的1* @param x 输入数值* @return x的最低位的1所代表的值*/
int lowbit(int x)
{return x & -x; // 利用补码性质
}/*** 树状数组单点更新操作* @param x 更新位置* @param c 增加的值*/
void add(int x, int c)
{// 树状数组标准更新操作for (int i = x; i <= n; i += lowbit(i))tr[i] += c;
}/*** 树状数组前缀和查询操作* @param x 查询位置* @return 前x个位置中在场人员的数量*/
int query(int x)
{int res = 0;// 树状数组标准查询操作for (int i = x; i; i -= lowbit(i))res += tr[i];return res;
}/*** 查找第k个在场人员的位置* @param k 要找的第k个在场人员* @return 第k个在场人员的实际位置*/
int find(int k)
{int l = 1, r = n; // 二分查找边界int ans; // 存储查找结果// 二分查找：找到前缀和>=k的最小位置while (l <= r){int mid = (l + r) >> 1; // 计算中点if (query(mid) >= k){ans = mid; // 记录当前位置r = mid - 1; // 继续向左查找更小的满足条件的位置}else {l = mid + 1; // 向右查找}}return ans;
}int main()
{// 输入总人数和报数间隔cin >> n >> m;// 初始化：所有人都在场for (int i = 1; i <= n; i++) add(i, 1);int pos = 1; // 当前位置指针，从第1个人开始// 循环n次，每次出列一个人for (int i = 1; i <= n; i++){// 计算剩余人数int rem = n - i + 1;// 计算下一个出列人员的位置（约瑟夫环公式）int k = (pos + m - 1) % rem; // 从当前位置开始数m个人if (k == 0) k = rem; // 如果余数为0，则取最后一个// 找到第k个在场人员的实际位置int target = find(k);// 输出出列人员cout << target << " ";// 标记该人员已出列add(target, -1);// 更新当前位置指针为当前出列位置pos = k;}return 0;
}
【运行结果】
10 3
3 6 9 2 7 1 8 5 10 4