算法

(模拟) $O(k\log n \log\log n)$

本题实际上是让我们求 $f^k(N)$，故只需做 $k$ 次 $N = f(N)$ 即可。此外，$g1$ 和 $g2$ 可以借助 $\rm vector$ 或 $\rm string$ 简单模拟出来。

C++ 代码

// 法1
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::sort;

vector<int> toDigits(int n) {
    vector<int> d;
    while (n) {
        d.push_back(n % 10);
        n /= 10;
    }
    return d;
}

int toInt(vector<int> d) {
    int res = 0;
    for (int i = d.size() - 1; i >= 0; --i) {
        res = res * 10 + d[i];
    }
    return res;
}

int g1(int n) {
    auto d = toDigits(n);
    sort(d.begin(), d.end());
    return toInt(d);
}

int g2(int n) {
    auto d = toDigits(n);
    sort(d.rbegin(), d.rend());
    return toInt(d);
}

int f(int n) {
    return g1(n) - g2(n);
}

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

    rep(i, k) n = f(n);

    cout << n << '\n';

    return 0;
}

// 法2
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); ++i)

using std::cin;
using std::cout;
using std::string;
using std::sort;
using std::to_string;

int g1(int n) {
    string s = to_string(n);
    sort(s.rbegin(), s.rend());
    return stoi(s);
}

int g2(int n) {
    string s = to_string(n);
    sort(s.begin(), s.end());
    return stoi(s);
}

int f(int n) {
    return g1(n) - g2(n);
}

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

    rep(i, k) n = f(n);

    cout << n << '\n';

    return 0;
}