解题思路

一瓶饮料 n 元，两个空瓶可以换一瓶新的。有 m 元，问最多能喝几瓶。

思路：先买，再递归换。

1. 先用 m 元买 m/n 瓶，得到 m/n 个空瓶
2. 两个空瓶换一瓶：x 个空瓶能换 x/2 瓶
3. 换来的 x/2 瓶喝完又产生 x/2 个空瓶，加上原来剩下的 x%2 个空瓶，继续换
4. 递归这个过程，直到空瓶不够两个

递归公式： fun(x) = x/2 + fun(x/2 + x%2)，x < 2 时返回 0。

举例：n=2，m=10

• 先买 10÷2 = 5 瓶
• 5 个空瓶换 2 瓶（剩 1 个空瓶），喝掉 2 瓶
• 3 个空瓶（2+1）换 1 瓶（剩 1 个），喝掉 1 瓶
• 2 个空瓶换 1 瓶，喝掉
• 总共 5+2+1+1 = 9 瓶

参考代码

#include <iostream>
using namespace std;

int fun(int x) {  // x 个空瓶换多少瓶
    if (x >= 2) {
        return x / 2 + fun(x / 2 + x % 2);
    } else {
        return 0;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    cout << m / n + fun(m / n) << endl;  // 买 + 换
    return 0;
}

复杂度分析

• 时间复杂度：O(log X)，每次空瓶减半
• 空间复杂度：O(log X)，递归深度