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 个）和标记最后一个苹果的位置。代码简洁且时间复杂度低，适合竞赛场景。掌握此类问题的解题思路，有助于提升对循环规律与数学优化的理解。