luogu-B3925 [GESP202312 三级] 小猫分鱼

GESP三级真题，多重循环和数学计算相关，难度★★☆☆☆。

luogu-B3925 [GESP202312 三级] 小猫分鱼

题目要求

题目描述

海滩上有一堆鱼，$N$ 只小猫来分。第一只小猫把这堆鱼平均分为 $N$ 份，多了 $i \lt N$ 个，这只小猫把多的 $i$ 个扔入海中，拿走了一份。第二只小猫接着把剩下的鱼平均分成 $N$ 份，又多了 $i$ 个，小猫同样把多的 $i$ 个扔入海中，拿走了一份。第三、第四、……，第 $N$ 只小猫仍是最终剩下的鱼分成 $N$ 份，扔掉多了的 $i$ 个，并拿走一份。

编写程序，输入小猫的数量 $N$ 以及每次扔到海里的鱼的数量 $i$，输出海滩上最少的鱼数，使得每只小猫都可吃到鱼。

例如：两只小猫来分鱼 $N=2$，每次扔掉鱼的数量为 $i=1$，为了每只小猫都可吃到鱼，可令第二只小猫需要拿走 $1$ 条鱼，则此时待分配的有 $3$ 条鱼。第一只小猫待分配的鱼有 $3\times 2+1=7$ 条。

输入格式

总共 $2$ 行。第一行一个整数 $N$，第二行一个整数 $i$。

保证 $0 \lt N \lt 10$；$i \lt N$ 。

输出格式

一行一个整数，表示满足要求的海滩上最少的鱼数。

输入输出样例 #1

输入 #1

2
1

输出 #1

7

输入输出样例 #2

输入 #2

3
1

输出 #2

25

说明/提示

样例解释 2:

三只小猫来分鱼 $N=3$，每次扔掉鱼的数量为 $i=1$，为了每只小猫都可吃到鱼，可令第三只小猫需要拿走 $3$ 条鱼（拿走 $1$ 条和 $2$ 条不满足要求），则此时待分配的有 $10$ 条鱼。第二只小猫待分配的鱼有 $10×3/2+1 = 16$ 条。第一只小猫待分配的鱼有 $16×3/2+1 = 25$ 条。

题目分析

解题思路

本题的解题思路可以分为以下几个步骤：

1. 读取输入数据：

   • 读取小猫数量N和每次扔掉的鱼的数量i
   • 确保输入数据满足题目约束条件：$0 \lt N \lt 10$ 且 $i \lt N$

2. 从小到大枚举可能的最后一只小猫的拿鱼数：

   • 使用一个循环，从较小的数开始尝试
   • 对于每个尝试的数，模拟N只小猫分鱼的过程
   • 记录每一步剩余的鱼数，直到最后一只小猫

3. 验证分鱼过程：

   • 从最后一只小猫开始，反向计算每一步需要的鱼数
   • 每一步都需要满足：
     • 鱼数能被N整除
     • 分完后还剩i条鱼
     • 每只小猫都能拿到至少1条鱼

复杂度分析：

• 时间复杂度：$O(M)$，其中M是最终答案的大小
• 空间复杂度：$O(1)$，只需要常数级别的额外空间

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>

int main() {
    // 声明变量n表示小猫数量，i表示每次扔掉的鱼的数量
    int n, i;
    // 从标准输入读取n和i
    std::cin >> n >> i;
    // 从1开始循环，寻找满足条件的最后一只小猫可能拿的最小鱼数
    for (int j = 1;; j++) {
        // flag标记是否找到满足条件的解
        bool flag = true;
        // result记录当前计算的鱼的数量
        int result = 0;
        // 模拟n只小猫分鱼的过程
        for (int k = 0; k < n; k++) {
            if (k == 0) {
                // 最后一只小猫拿前的情况：初始鱼数 = j * n + i
                result = j * n + i;
                continue;
            }
            // 检查剩余的鱼是否能被(n-1)整除
            if (result % (n - 1) != 0) {
                // 不能整除则当前j值不是解
                flag = false;
                break;
            } else {
                // 计算下一只小猫面对的鱼数
                // 先将鱼平均分成n-1份，再乘以n（因为要分n份），最后加上多余的i条
                result = result / (n - 1) * n + i;
            }
        }
        // 如果找到解，输出结果并退出循环
        if (flag) {
            std::cout << result;
            break;
        } else {
            // 未找到解，继续尝试下一个j值
            continue;
        }
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

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