P4386 猴子吃桃（基础）

解题思路

猴子每天吃"剩下桃子的一半再加 1 个"，第 n 天早上醒来发现只剩 1 个桃子，问第一天买了几个。

顺着想很难，因为不知道开头有多少。但可以"倒着想"：第 n 天早上剩 1 个，那么第 n-1 天早上应该有多少？第 n-1 天早上吃掉"一半加 1 个"后剩 1 个，也就是说：(前一天早上的数) - (前一天早上的数 ÷ 2) - 1 = 1，整理一下得到：前一天早上的数 = (1 + 1) × 2 = 4 个。

所以倒推公式是：前一天早上 = (当天早上 + 1) × 2。只要从第 n 天（剩 1 个）往前倒推 n-1 次，就回到了第 1 天早上，也就是猴子买的桃子数。

拿样例 n=4 验证：第 4 天早上 1 个；第 3 天早上 (1+1)×2 = 4 个；第 2 天早上 (4+1)×2 = 10 个；第 1 天早上 (10+1)×2 = 22 个。所以猴子买了 22 个桃子，和样例一致。

边界情况：n 最小是 1，这时第 1 天早上就剩 1 个，说明买了 1 个，一次都不用倒推，代码里的 for 循环条件 i < n 会自然跳过。倒推过程中数字越变越大，用 long long 更保险。

参考代码

// 程序用途：倒推计算猴子第一天早上买了多少个桃子
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long x = 1;                  // 第n天早上还剩下1个桃子
    // 每天吃"剩余的一半再加一个"，所以倒推：前一天早上 = (当天早上 + 1) * 2
    for (int i = 1; i < n; i++) x = (x + 1) * 2;
    cout << x << endl;                // 倒推到第1天早上就是买的数量
    return 0;
}

复杂度分析

从第 n 天倒推到第 1 天，一共循环 n-1 次，时间复杂度是 O(n)；空间上只用了几个变量，额外空间复杂度是 O(1)。