Portal

Solution:

Look directly at the hard version. I feel that easy is not very different from the hard version. To get the minimum k-beautiful number, it can be divided into the following two cases.

• First of all, if K is greater than or equal to the number of different bits after n is converted into a string, then directly output this n. this n itself is k-beautiful, not to mention the smallest, so it must be output.
• Secondly, K is less than the different digits after n is converted into a string. In order to minimize the k-beautiful number, the first few digits of n should remain unchanged as far as possible. If it remains unchanged at the ith bit of n (from high to low digits), the different digits used will become k + 1, which is very bad. At this time, there are two situations.
  • First, consider whether there is a number larger than the number on the i-th bit in the k digits used previously. If so, take the closest one, For all the bits after I, we take the smallest of the k digits used to supplement (the proof is as follows: if we don't take it this way, or add 1 to the i-th bit, then some bits of the k digits used earlier must be larger, which will make the answer larger.)
  • However, if this number is not found in the K digits used previously, we have to consider moving forward from the I-1 bit. For example, when we get to the I-1 bit, we first remove the I-1 bit, and we have to maintain the contribution of the digit on this bit to K. if there is only one digit on this I-1 bit, then the number used is k-1, But there is also this digit in the high position in front. At this time, K is still unchanged. This can be divided into three cases.
    • If the k used at this time is less than the k required by the question, maintain the answer of the I-1 bit as the previous digit plus 1, and maintain the digit + 1 to the used k. if k has been used up, use the smallest digit in k to supplement all the subsequent digits, otherwise k has not been used up, Then use 0 to supplement all the following digits (this is handled in a robust way, because it is possible that digit + 1 and the second case below will be encountered).
    • Otherwise, after i - 1 processing, it is found that the k used is still not reduced, so consider whether other digits in the k digits used are greater than the digit on the i - 1 bit. If so, the process is to change the digit on the i - 1 bit into the k digits closest to and greater than the digit on the i - 1 bit. If the subsequent digits have been used up, use the smallest digit in the k to supplement all the subsequent digits. Otherwise, if k has not been used up, use 0 to supplement all the subsequent digits.
    • The last one is that in the previous second case, if the digit larger than the digit on i - 1 is not found, then the i - 2 bit must be considered again. The processing is the same as that of i - 1.

#include <bits/stdc++.h>
#define ll long long
#define rush() int T; cin >> T; while (T--)
using namespace std;
int n, k, num, cnt[10];
string s;
int main()
{
    rush() {
        num = 0;
        for (int i = 0; i < 10; i++) cnt[i] = 0;
        cin >> n >> k;
        s = to_string(n);
        int ssize = s.size();
        for (int i = 0; i < ssize; i++) {
            if (cnt[s[i] - '0'] == 0) num++;
            cnt[s[i] - '0']++;
        }
        if (num <= k) cout << n << endl;
        else {
            set<int>se;
            map<char, int>ma;
            string ans = "";
            for (int i = 0; i < ssize; i++) {
                char c = s[i];
                ma[c] += 1;
                se.insert(c);
                if (se.size() <= k) ans += c;
                else {
                    se.erase(c);
                    ma[c] -= 1;
                    if (ma[c] == 0) se.erase(c);
                    auto iter = se.upper_bound(c);
                    if (iter != se.end()) {
                        ans += *iter;
                        for (int j = ans.size(); j < ssize; j++) {
                            if (se.size() < k) ans += '0';
                            else ans += *(se.begin());
                        }
                        break;
                    } else {
                        while (233) {
                            c = ans.back();
                            ma[c] -= 1;
                            ans.pop_back();
                            if (ma[c] == 0) se.erase(c);
                            if (se.size() < k) {
                                ans += c + 1;
                                ma[c + 1] += 1;
                                se.insert(c + 1);
                                for (int j = ans.size(); j < ssize; j++) {
                                    if (se.size() < k) ans += '0';
                                    else ans += *(se.begin());
                                }
                                break;
                            } else {
                                iter = se.upper_bound(c);
                                if (iter != se.end()) {
                                    ans += *iter;
                                    for (int j = ans.size(); j < ssize; j++) {
                                        if (se.size() < k) ans += '0';
                                        else ans += *(se.begin());
                                    }
                                    break;
                                }
                            }
                        }
                        break;
                    }
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}