小O的整数操作

[题目链接](https://www.nowcoder.com/practice/52e3cbb106d54366a3f5fefac03d169f)

题目理解

给定整数 、目标值 和除数 ，每次可以执行以下操作之一：

1. 
2. （仅当 时）

求将 变为 的最少操作次数。

思路：贪心

关键观察：每次除以 能将 快速缩小，而减 1 每次只减少 1。因此，只要除以 不会让 低于目标值 ，就应该尽量利用除法。

贪心策略：从 出发，每一步：

1. 若 ，无法通过除法缩小 ，只能减法：答案 ，结束。
2. 若 能被 整除，且 ：执行一次除法（操作数 ，）。
3. 若 （除法会越过目标）：只能减法，答案 ，结束。
4. 否则（ 不能被 整除，且 ）：先减法到 （即 以下最大的 的倍数），再执行情形 2。

正确性分析：当 时，除以 一步就替代了 次减法，所以除法永远不劣于减法。只有当除以 会使结果低于 时，才改为减法直接到达 。

样例演示

输入 10 4 2：

• ，，，除法：，ops=1
• ，，，划不来（）：减到 ，ops=2
• ，结束

输出 2，正确。

时间复杂度

每次执行除法时， 至少缩小为原来的 。两次除法之间至多执行 次减法。总循环次数为 ，整体时间复杂度 。

代码

C++

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    long long ops = 0;

    while (n > t) {
        if (k == 1) {
            ops += n - t;
            n = t;
            break;
        }

        if (n % k == 0 && n / k >= t) {
            ops++;
            n /= k;
        } else if (n / k < t) {
            ops += n - t;
            n = t;
        } else {
            long long next_div = (n / k) * k;
            if (next_div >= t) {
                ops += n - next_div;
                n = next_div;
            } else {
                ops += n - t;
                n = t;
            }
        }
    }

    cout << ops << endl;
    return 0;
}

Java

import java.util.Scanner;

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

        long ops = 0;

        while (n > t) {
            if (k == 1) {
                ops += n - t;
                n = t;
                break;
            }

            if (n % k == 0 && n / k >= t) {
                ops++;
                n /= k;
            } else if (n / k < t) {
                ops += n - t;
                n = t;
            } else {
                long next_div = (n / k) * k;
                if (next_div >= t) {
                    ops += n - next_div;
                    n = next_div;
                } else {
                    ops += n - t;
                    n = t;
                }
            }
        }

        System.out.println(ops);
    }
}