luogu-P2696 慈善的约瑟夫

GESP C++ 五级练习题，算法数学和模拟算法考点应用，重点理解约瑟夫问题。五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P2696 慈善的约瑟夫

题目要求

题目描述

你一定听说过约瑟夫问题吧？即从 $N$ 个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏，假设 $N$ 个人站成一圈，从第 $1$ 人开始交替的去掉游戏者，但只是暂时去掉，直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人得到 $1$ 个金币，永久性离开。其余剩下的将重复以上的游戏过程，比幸存者号码大的人每人得到 $1$ 个金币后离开。经过若干轮这样的过程后，一旦人数不再减少，则最后剩下的那些人将得到 $2$ 个金币。请你计算一下老约瑟夫一共要付出多少钱？

输入格式

一行一个正整数 $N$ 表示人数。

输出格式

一行一个正整数表示共需支付的钱数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

$1\le N \le 10^5$

题目分析

这道题是经典的约瑟夫问题（Josephus Problem）的一个变种，结合了模拟和数学推导。

1. 题目核心解析

题目描述了一个重复进行的游戏过程，我们可以将其分解为以下几个关键点：

初始状态： $N$ 个人围成一圈，编号 $1$ 到 $N$ 。
约瑟夫游戏规则：从第 1 人开始交替去掉游戏者。这实际上是经典的 $K=2$ （每隔一个人踢出一个）的约瑟夫问题。
每一轮的结算：
1. 找出唯一的幸存者（记为 $S$ ）。
2. 所有编号大于 $S$ 的人离开游戏，每人获得 $1$ 个金币。
3. 剩下的人（编号 $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$ $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$ 的数据规模。

拓展知识：约瑟夫问题详解

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$ 。答案正确，简单易懂！

示例代码

/*
 * 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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月4日

luogu-P12733 磨合

luogu-P2696 慈善的约瑟夫