【GESP】C++三级真题 luogu-B3925 [GESP202312 三级] 小猫分鱼
GESP三级真，多重循环和数学计算相关，难度★★☆☆☆。
luogu-B3925 [GESP202312 三级] 小猫分鱼
题目要求
题目描述
海滩上有一堆鱼，$N$ 只小猫来分。第一只小猫把这堆鱼平均分为 $N$ 份，多了 $i<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<N<10$；$i<N$ 。
输出格式
一行一个整数，表示满足要求的海滩上最少的鱼数。
输入输出样例 #1
输入 #1
1
2
2
1
输出 #1
1
7
输入输出样例 #2
输入 #2
1
2
3
1
输出 #2
1
25
说明/提示
样例解释 2:
三只小猫来分鱼 $N=3$，每次扔掉鱼的数量为 $i=1$，为了每只小猫都可吃到鱼，可令第三只小猫需要拿走 $3$ 条鱼（拿走 $1$ 条和 $2$ 条不满足要求），则此时待分配的有 $10$ 条鱼。第二只小猫待分配的鱼有 $10×3/2+1 = 16$ 条。第一只小猫待分配的鱼有 $16×3/2+1 = 25$ 条。
题目分析
解题思路
本题的解题思路可以分为以下几个步骤：
- 读取输入数据：
- 读取小猫数量N和每次扔掉的鱼的数量i
- 确保输入数据满足题目约束条件：$0<N<10$且$i<N$
- 从小到大枚举可能的初始鱼数：
- 使用一个循环，从较小的数开始尝试
- 对于每个尝试的数，模拟N只小猫分鱼的过程
- 记录每一步剩余的鱼数，直到最后一只小猫
- 验证分鱼过程：
- 从最后一只小猫开始，反向计算每一步需要的鱼数
- 每一步都需要满足：
- 鱼数能被N整除
- 分完后还剩i条鱼
- 每只小猫都能拿到至少1条鱼
复杂度分析：
- 时间复杂度：$O(M)$，其中M是最终答案的大小
- 空间复杂度：$O(1)$，只需要常数级别的额外空间
示例代码
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
#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;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。