题解 | #小O的整数操作#

题目链接

小O的整数操作

题目描述

给定三个整数 $n$ , $m$ , 和 $k$ 。初始时我们有一个数字 $n$ ，目标是将其变为 $m$ 。

我们有两种操作：

将当前数字减去 1。
如果当前数字能被 $k$ 整除，可以将其除以 $k$ 。

求解将 $n$ 变为 $m$ 所需的最少操作次数。

解题思路

这是一个典型的最短路问题，可以使用广度优先搜索（BFS）求解。然而，通过分析操作的性质，我们可以发现一个更高效的贪心策略。

我们的目标是从 $n$ 变换到 $m$ （题目隐含 $n \ge m$ ）。操作 /k 能比 -1 更快地减小数值，因此我们的核心思想是尽可能多地使用 /k 操作。

贪心策略

我们可以从 $n$ 开始，逐步向 $m$ 靠近。在每一步，我们做出最优的局部选择：

当 $n > m$ 时，循环执行以下逻辑：
- 情况一： $n$ 可以被 $k$ 整除 在这种情况下，我们有两个选择： a. 执行一次除法操作：n = n / k，操作数加 1。 b. 执行一次减法操作：n = n - 1，操作数加 1。为了尽快到达 $m$ ，选择除法操作显然更优。它一步跨越的数值范围远大于减法。
- 情况二： $n$ 不可以被 $k$ 整除 此时，我们别无选择，只能执行减法操作。为了能够尽快地使用除法操作，我们应该将 $n$ 减到上一个（即小于等于当前 $n$ 的） $k$ 的倍数。
  - 需要减去的数值是 n % k。
  - 但是，我们需要考虑目标 $m$ 。如果 n - (n % k) 的结果小于 $m$ ，那么我们就不能通过“先减再除”的方式跨过 $m$ 。此时，唯一的路径就是从当前的 $n$ 一直减到 $m$ 。这种情况下，剩余的操作数就是 n - m，我们可以直接加上这个值然后结束计算。
  - 如果 n - (n % k) 大于或等于 $m$ ，那么我们就安全地执行 n % k 次减法操作。
当 $n \le m$ 时：由于我们的操作只能减小 $n$ ，所以此时唯一的可能是 $n = m$ 。循环结束，我们得到了最终的操作数。

综上，算法流程如下：

初始化操作数 count = 0。
当 n > m 时：
- 如果 n % k == 0，则 n = n / k，count 加 1。
- 否则，计算 rem = n % k。如果 n - rem < m，则 count += (n - m)，然后 n = m，结束。否则，count += rem，并且 n -= rem。
返回 count。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n, m, k;
    cin >> n >> m >> k;

    long long count = 0;
    if (n <= m) {
        cout << m - n << endl;
        return 0;
    }

    while (n > m) {
        if (n % k == 0) {
            long long next_n = n / k;
            if (next_n >= m) {
                n = next_n;
                count++;
            } else {
                count += (n - m);
                n = m;
            }
        } else {
            long long rem = n % k;
            long long next_n_base = n - rem;
            if (next_n_base >= m) {
                count += rem;
                n -= rem;
            } else {
                count += (n - m);
                n = m;
            }
        }
    }

    cout << count << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        long k = sc.nextLong();

        if (n <= m) {
            System.out.println(m - n);
            return;
        }

        long count = 0;
        while (n > m) {
            if (n % k == 0) {
                long nextN = n / k;
                if (nextN >= m) {
                    n = nextN;
                    count++;
                } else {
                    count += (n - m);
                    n = m;
                }
            } else {
                long rem = n % k;
                long nextNBase = n - rem;
                if (nextNBase >= m) {
                    count += rem;
                    n -= rem;
                } else {
                    count += (n - m);
                    n = m;
                }
            }
        }
        System.out.println(count);
    }
}

def main():
    n, m, k = map(int, input().split())

    if n <= m:
        print(m - n)
        return

    count = 0
    while n > m:
        if n % k == 0:
            next_n = n // k
            if next_n >= m:
                # 如果除法后仍然不小于m，可以安全地执行
                # 但需要比较是直接减到底划算，还是一步除法+后续操作划算
                # 实际上，一步除法总是更优的
                count += 1
                n = next_n
            else:
                # 除法会越过m，直接计算减法次数
                count += (n - m)
                n = m
        else:
            rem = n % k
            next_n_base = n - rem
            if next_n_base >= m:
                count += rem
                n -= rem
            else:
                count += (n - m)
                n = m
    
    print(count)

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心算法
时间复杂度：在循环的每一步中，如果执行除法，n 会迅速减小。如果执行减法，n 会减小 n % k（最多 k-1），紧接着下一步就是除法。因此，n 的值呈对数级下降。总时间复杂度为 $\mathcal{O}(k \cdot \log_k n)$ 。
空间复杂度：该算法只使用了有限的几个变量来存储状态，因此空间复杂度为 $\mathcal{O}(1)$ 。