【GESP】C++五级练习题 luogu-P2696 慈善的约瑟夫
GESP C++ 五级练习题，算法数学和模拟算法考点应用，重点理解约瑟夫问题。五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
luogu-P2696 慈善的约瑟夫
题目要求
题目描述
你一定听说过约瑟夫问题吧？即从 $N$ 个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏，假设 $N$ 个人站成一圈，从第 $1$ 人开始交替的去掉游戏者，但只是暂时去掉，直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人得到 $1$ 个金币，永久性离开。其余剩下的将重复以上的游戏过程，比幸存者号码大的人每人得到 $1$ 个金币后离开。经过若干轮这样的过程后，一旦人数不再减少，则最后剩下的那些人将得到 $2$ 个金币。请你计算一下老约瑟夫一共要付出多少钱？
输入格式
一行一个正整数 $N$ 表示人数。
输出格式
一行一个正整数表示共需支付的钱数。
输入输出样例 #1
输入 #1
1
10
输出 #1
1
13
说明/提示
$1\le N \le 10^5$
题目分析
这道题是经典的约瑟夫问题（Josephus Problem）的一个变种，结合了模拟和数学推导。
1. 题目核心解析
题目描述了一个重复进行的游戏过程，我们可以将其分解为以下几个关键点：
- 初始状态：$N$ 个人围成一圈，编号 $1$ 到 $N$。
- 约瑟夫游戏规则：从第 1 人开始交替去掉游戏者。这实际上是经典的 $K=2$（每隔一个人踢出一个）的约瑟夫问题。
- 每一轮的结算：
- 找出唯一的幸存者（记为 $S$）。
- 所有编号大于 $S$ 的人离开游戏，每人获得 $1$ 个金币。
- 剩下的人（编号 $1$ 到 $S$）进入下一轮，人数变为 $S$。
- 终止条件：当人数不再减少时（即本轮没有比幸存者编号更大的人，也就是 $S == N$），游戏结束。
- 最终奖励：最后留下的 $N$ 个人（此时不再减少），每人获得 $2$ 个金币。
2. 数学原理：约瑟夫问题 ($K=2$) 幸存者公式
这道题的核心在于如何快速求出 $N$ 个人中，$K=2$ 时的幸存者编号。这是一个经典的数学问题，有 $O(1)$ 的公式解法。
假设 $J(n)$ 表示 $n$ 个人进行 $K=2$ 约瑟夫游戏时的幸存者编号（1-indexed）。公式如下： \(J(n) = 2 \times (n - 2^m) + 1\) 其中 $2^m$ 是不超过 $n$ 的最大 2 的幂（即 $2^m \le n$）。
公式直观理解：
- $2^m$ 可以理解为把 $n$ 的二进制最高位去掉后的剩余部分，再左移一位加 1。
- 例如 $N=10$：
- 不超过 10 的最大 2 的幂是 $8$ ($2^3$)。
- $S = 2 \times (10 - 8) + 1 = 2 \times 2 + 1 = 5$。
- 所以 10 个人玩，幸存者是 5 号。
3. 解题过程模拟
我们以样例 $N=10$ 为例来验证这个逻辑：
- 第 1 轮：
- 当前人数 $N=10$。
- 计算幸存者：$2 \times (10 - 8) + 1 = 5$。
- 离开的人：编号 $6, 7, 8, 9, 10$，共 $10 - 5 = 5$ 人。
- 支付金币：$5 \times 1 = 5$。
- 剩余人数更新为 $N=5$。
- 第 2 轮：
- 当前人数 $N=5$。
- 不超过 5 的最大 2 的幂是 4。
- 计算幸存者：$2 \times (5 - 4) + 1 = 3$。
- 离开的人：编号 $4, 5$，共 $5 - 3 = 2$ 人。
- 支付金币：$2 \times 1 = 2$。
- 累积金币：$5 + 2 = 7$。
- 剩余人数更新为 $N=3$。
- 第 3 轮：
- 当前人数 $N=3$。
- 不超过 3 的最大 2 的幂是 2。
- 计算幸存者：$2 \times (3 - 2) + 1 = 3$。
- 离开的人：$3 - 3 = 0$ 人。
- 终止条件触发：人数不再减少。
- 最终结算：
- 剩下的 $3$ 人，每人得 $2$ 金币。
- 支付金币：$3 \times 2 = 6$。
- 总金币：$7 + 6 = 13$。
结果与样例输出 13 一致。
4. 代码逻辑分析
- 辅助函数
get_survivor(int n)：- 利用
while(2 * l <= n) l *= 2;找到不超过 $n$ 的最大 2 的幂 $l$。 - 直接套用公式返回幸存者编号。这一步避免了 $O(N)$ 的模拟，将复杂度降为 $O(\log N)$。
- 利用
- 主循环
while(true)：- 每次调用
get_survivor算出幸存者。 - 计算离开人数
leave_count = n - survivor。 - 如果
leave_count == 0，说明幸存者就是最后一个人（或者说编号和人数相等，没人离开），跳出循环。 - 否则，累加金币
total += leave_count，并更新n = survivor。
- 每次调用
- 时间复杂度：
- 每一轮 $N$ 都会显著减小（通常减半或变为 $2^k-1$），轮数非常少（对数级别）。
get_survivor自身也是对数复杂度。总体复杂度极低，完全可以处理 $N=10^5$ 的数据规模。
- 每一轮 $N$ 都会显著减小（通常减半或变为 $2^k-1$），轮数非常少（对数级别）。
拓展知识：约瑟夫问题详解
1. 问题背景
约瑟夫问题（Josephus Problem）是一个著名的数学问题，起源于公元1世纪的历史学家弗拉维奥·约瑟夫斯（Flavius Josephus）的传说。故事中，约瑟夫斯和他的40名战友被罗马军队包围在洞穴中，他们决定宁死不降，于是商定了一种自杀方式：大家围成一个圈，从某个人开始报数，每报到第 $K$ 个人，该人就必须自杀，然后下一个人重新开始报数，直到所有人都自杀身亡。约瑟夫斯为了活下来，运用数学知识算出了最后一个幸存者的位置。
在计算机科学中，这个问题通常被抽象为：$N$ 个人围成一圈，编号为 $1, 2, \dots, N$，从第 1 个人开始报数，数到 $K$ 的人出列，下一个人重新从 1 开始报数，直到最后剩下一个人。
2. K=2 代表什么？
$K$ 代表报数的步长。
- 当 $K=2$ 时，意味着每隔一个人踢出一个人。
- 报数过程是：1(留), 2(踢), 3(留), 4(踢)… 即第一个人报 1，第二个人报 2（出列），第三个人报 1，第四个人报 2（出列）……
- 这是约瑟夫问题最经典也是最特殊的情况，因为它可以通过二进制操作快速求解。
3. 答案公式的基本推导理解逻辑 ($K=2$)
我们可以通过观察 $N$ 较小时的幸存者编号，找出一套非常简单的规律，适合小学生理解。
第一步：列出数据找规律 我们手动模拟一下前几个数字的幸存者：
| 总人数 $N$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 幸存者 $J(N)$ | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
第二步：发现规律 通过观察上面的表格，我们可以发现两个非常明显的现象：
- 归零点（重置点）：当 $N$ 是 2 的幂次方（如 $1, 2, 4, 8, 16, 32 \dots$）时，幸存者总是 第 1 号。
- $N=2$ (即 $2^1$) $\rightarrow$ 幸存者 1
- $N=4$ (即 $2^2$) $\rightarrow$ 幸存者 1
- $N=8$ (即 $2^3$) $\rightarrow$ 幸存者 1
- $N=16$ (即 $2^4$) $\rightarrow$ 幸存者 1
- 递增规律：在两个“归零点”之间，人数 $N$ 每增加 1，幸存者的编号就增加 2。例如从 $N=8$ 到 $N=10$：
- $N=8$ 是归零点，幸存者为 1。
- $N=9$ 比 8 多 1 人，幸存者变为 $1 + 2 = 3$。
- $N=10$ 比 8 多 2 人，幸存者变为 $3 + 2 = 5$。
第三步：总结公式
根据上面的规律，想知道 $N$ 个人的幸存者是谁，只需要看 $N$ 比“最近的那个 2 的幂次方”多出了多少人。
假设 $2^m$ 是不超过 $N$ 的最大 2 的幂（也就是最近的那个“归零点”）。 多出来的人数 $L = N - 2^m$。 因为每多 1 个人，编号加 2，所以幸存者编号就是： \(J(N) = 2 \times L + 1\) 即： \(J(N) = 2 \times (N - 2^m) + 1\)
举例验证：如果 $N=10$：
- 不超过 10 的最大 2 的幂是 $8$ （即 $2^3$）。
- 多出来的人数 $L = 10 - 8 = 2$。
- 幸存者编号 $= 2 \times 2 + 1 = 5$。 答案正确，简单易懂！
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
* P2696 慈善的约瑟夫
* 题目链接：https://www.luogu.com.cn/problem/P2696
*
* 核心思路：
* 1. 每一轮游戏是 K=2 的约瑟夫问题变种。
* 2. 幸存者编号公式：J(n) = 2 * (n - 2^m) + 1，其中 2^m <= n。
* 3. 每一轮比幸存者编号大的人离开，离开的人每人得 1 金币。
* 4. 剩下的人数变为幸存者编号，继续下一轮。
* 5. 当人数不再减少时，游戏结束，剩下的人每人得 2 金币。
*/
#include <iostream>
// 计算 N 个人每隔 1 人踢出 1 人后的幸存者编号 (K=2)
// 公式: J(n) = 2 * (n - 2^m) + 1, 其中 l = 2^m 是不超过 n 的最大 2 的幂
int get_survivor(int n) {
if (n == 1) {
return 1;
}
int l = 1;
while (2 * l <= n) {
l *= 2;
}
return 2 * (n - l) + 1;
}
int main() {
int n;
std::cin >> n;
// 总金币数，累加项，使用 long long 防止溢出
long long total = 0;
while (true) {
// Step 1: 计算当前人数 n 下的幸存者编号
int survivor = get_survivor(n);
// Step 2: 规则是“比幸存者号码高的人离开”
// 即编号为 survivor+1 到 n 的人离开
int leave_count = n - survivor;
// 如果没有人离开（即所有人都留下了），循环结束
if (leave_count == 0) {
break;
}
// Step 3: 离开的人每人得到 1 个金币
total += leave_count;
// Step 4: 更新剩下的人数（剩下 survivor 个人）
n = survivor;
}
// 最后剩下的人每人得到 2 个金币
total += n * 2;
std::cout << total << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
