2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析
一、题目解读
CSP-J 2023年的小苹果题目(对应洛谷P9748)是一个经典的动态规划问题。题目描述了一个苹果被依次取走的场景:每天取走当前苹果数量的 (n-1)/3 + 1 个苹果,直至全部取完。需要计算两个关键值:总天数和最后一个苹果被取走的天数。该题目考验对循环规律的观察与数学推导能力,需通过编程实现高效的解题逻辑。
二、解题思路
作者提供的代码采用循环模拟与标记法解决该问题。核心思路为:
1. 天数递增与取苹果逻辑:通过循环模拟每天的操作,每次计算取走的苹果数为 (n-1)/3 + 1。
2. 关键节点标记:当剩余苹果数满足 (n-1) % 3 == 0 时,说明当前轮次取走最后一个苹果,记录天数。
3. 动态更新剩余苹果数:通过数学推导优化,避免直接模拟取苹果过程,提升效率。
三、解题步骤解析
1. 初始化变量:
n 为苹果总数,days 初始化为0,last_day 记录关键天数,found 标记是否找到目标苹果。
2. 循环模拟取苹果过程:
每天 (days++) 计算取走数量 (n-1)/3 + 1,更新剩余苹果数 n -=...。
3. 判断关键节点:
当 n-1 为3的倍数时,说明当前取走最后一个苹果,记录天数并标记 found。
4. 终止条件:当 n=0 时,循环结束,输出总天数和关键天数。
四、代码与注释
#include <iostream> using namespace std; int main() { int n; // 苹果总数 cin >> n; int days = 0; // 总天数 int last_day = 0; // 第n个苹果被取走的天数 bool found = false; // 是否已找到第n个苹果 while (n > 0) { days++; // 天数增加 // 检查当前轮次是否取走第n个苹果 if (!found && (n - 1) % 3 == 0) { last_day = days; found = true; } // 计算本轮取走的苹果数:(n-1)/3 + 1 n -= ((n - 1) / 3 + 1); } cout << days << " " << last_day << endl; return 0; }
注释说明:代码通过循环与条件判断,结合数学推导简化计算,高效求解目标天数。
五、总结
该题目通过动态规划思想,将复杂模拟转化为数学逻辑推导。关键点在于识别取苹果的规律(每轮取走 (n-1)/3 + 1 个)和标记最后一个苹果的位置。代码简洁且时间复杂度低,适合竞赛场景。掌握此类问题的解题思路,有助于提升对循环规律与数学优化的理解。
原创内容 转载请注明出处