Peter 的烟

题意

Peter 一开始有 n 根烟。每吸完一根烟会留下一个烟蒂，k 个烟蒂可以换一根新烟。求最终一共能吸到多少根烟。

思路

先看一个可以直接验证想法的朴素解：

直接模拟兑换过程即可。初始答案就是 n，然后只要当前烟蒂数不少于 k，就继续兑换。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    cin >> n >> k;

    long long ans = n;
    while (n >= k) {
        long long extra = n / k;
        ans += extra;
        n = extra + n % k;
    }

    cout << ans << '\n';
    return 0;
}

每轮兑换时，n / k 根新烟会带来 n / k 个新烟蒂，和剩下的 n % k 个烟蒂合在一起，就是下一轮的烟蒂数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    cin >> n >> k;

    long long ans = n;
    while (n >= k) {
        long long extra = n / k;
        ans += extra;
        n = extra + n % k;
    }

    cout << ans << '\n';
    return 0;
}

复杂度

每一轮烟蒂数都会减少，所以循环次数很少。时间复杂度可以看作 $O(log_k n)$ ，空间复杂度是 $O(1)$ 。

总结

这题的核心就是把“烟蒂换烟”写成一个循环更新公式。

目录

题意

思路

代码

复杂度

总结