《小猫分鱼大冒险》一、️ 故事开始海滩上的鱼山在阳光灿烂的海边有刚刚捕获的一大堆鱼 。突然来了很多只小猫它们决定按规则分鱼1、 分鱼规则假设有n只小猫。每一只小猫轮到时都要这样做第一步先看鱼堆把鱼平均分成n份。第二步如果多出i条鱼把多出的i条扔回大海 第三步拿走其中一份剩下的鱼留给下一只小猫。2、 任务目标输入小猫数量n每次扔掉的鱼数i输出最少一开始需要多少条鱼才能让所有小猫都成功分鱼3、 题目样例输入2 1表示一共有2只小猫每次都是多1条鱼扔掉输出74、 为什么答案是 71 第一只小猫来啦鱼有 7 条分给 2 只猫7 ÷ 2 3份还多1条把1条扔海里 剩下6条3条 3条第一只猫拿走3条。剩下3条2 第二只小猫来了3 条鱼分2份3 ÷ 2 1份多1条扔掉1条再拿走1条。成功3所以答案是7 这道题目应该怎么做二、 思路使用枚举模拟检查法从最小数字开始试1,2,3,4,5,6,7...谁第一次成功谁就是答案1、 判断一次是否成功的方法假设当前有fish条鱼。每只猫都检查条件1能多出 i 条也就是fish % n i条件2扔掉后还能平均分剩下fish - i必须能被 n 整除。条件3猫拿走一份后更新鱼数每份是(fish - i) / n猫拿走一份后还剩fish fish - i - 每份2、✨ 举个例子7条鱼fish 7 n 2 i 1第一只猫7 % 2 1 ✔扔1条后剩6每份3条拿走3条剩3条第二只猫3 % 2 1 ✔成功3、 参考程序#include iostream using namespace std; int main() { long long n, i; cin n i; long long fish 1; // 从1开始试 while(true) { long long temp fish; // 临时鱼堆 bool ok true; // 每只猫都来试一次 for(int cat 1; cat n; cat) { // 条件不满足 if(temp % n ! i || temp i) { ok false; break; } long long one (temp - i) / n; // 一份鱼 temp temp - i - one; // 剩余鱼 } if(ok) { cout fish; break; } fish; } return 0; }4、 程序一步一步解释第1步 读入数据cin n i;输入2 1第2步 从1开始尝试fish 1如果失败fish继续试第3步 每只猫来分鱼for(...)让每只猫依次登场 第4步 找到答案就输出cout fish;5⏱️ 时间复杂度假设答案是 X小猫数是 nO(X × n)意思试很多数字每个数字让 n 只猫检查三、 思路逆推模拟法前面写的是从小到大试答案→ 这是枚举 模拟检查我们现在根据最后一轮反推上一轮鱼数逐层构造答案→逆推模拟法1、 这个方法更像“模拟法”因为它不是盲目试1,2,3,4,5...而是先假设最后一只猫分鱼时的状态然后一步一步推回到第一只猫开始前的鱼数。这相当于按规则“搭积木”。2、 核心公式讲解1 最后一轮剩下的鱼设最后一只猫分鱼前有fish k * n i意思能分成n份多出i条鱼k表示每份有多少条2 这一轮分完后会剩多少扔掉i条后剩k*n每只猫拿走一份k剩下k*n - k k(n-1)这就是“下一轮看到的鱼”。3 反推上一轮公式如果当前这一轮开始前鱼数是fish那么上一轮开始前鱼数应满足prev - i分成n份拿走一份后剩下当前fish整理后可得prev fish * n / (n - 1) i前提是fish % (n - 1) 0否则不能整除不合法。3、 参考程序#include iostream using namespace std; int main() { long long n, i; cin n i; long long k 1; while (true) { bool ok true; // 最后一只猫分鱼前的鱼数 long long fish k * n i; // 反推前面 n-1 只猫 for (int round 1; round n; round) { if (fish % (n - 1) ! 0) //检查下是否整除判断合理性。 { ok false; break; } fish fish * n / (n - 1) i; } if (ok) { cout fish endl; break; } k; } return 0; }4、 详细讲解1 输入2 1表示2只猫每次扔1条鱼2 第一次尝试k1最后一只猫分鱼前fish 1*21 3说明最后一只猫看到3条鱼。往前推第一只猫开始前检查3 % (2-1) 0成立。反推fish 3 * 2 / 1 1 7已经推了n-11次结束。答案就是73 三只猫例子输入3 1k1最后一轮fish 1*31 4往前推时可能失败。k3 时成功最后一轮fish 3*31 10往前推两次10 - 16 - 25所以答案255、 为什么这个方法更好相比从1开始枚举1,2,3,4,5...这个方法直接从合法末状态出发速度更快四、 两种方法区别总结方法思路特点枚举检查法从1开始试每个答案直观容易懂反推模拟法从最后一轮反推第一轮更巧妙更快五、 算法知识1、 模拟法按照要求去操作就是模拟法这题就是经典模拟题2、 枚举法一个一个试答案1,2,3,4...这叫枚举法3、 记忆口诀自己能模拟就让电脑模拟跑不会模拟就从小开始找第一个成功就是宝