Codeforces Round #739 (Div. 3) F. Nearest Beautiful Number（思维、贪心）

• 题目：Nearest Beautiful Number
• 题意：给出一个数\(n (1 \leq n \leq 10^9 )\)和一个\(k(1 \leq k \leq 10)\)，使得\(x \geq\) n，并且至多存在k位不同的数字，求\(x\)的最小值。
• 解析：可以把这个数n看成一个串，先用一个set来存一下该串，判断不同的数字个数是否 \(\leq k\)，若满足则n即为答案；若不满足：
  • 首先找到找到第一个使得n有大于k个不同数的位置\(pos\)（从0开始），假如\(n = 6421, k = 2\)，那么得到\(pos\) = 2，因为前面已经满足有\(k\)种数，并且我们一开始也判断n数字组成的种类为4（分别为：6、4、2、1），那么可以肯定，\(pos\)位置的数无论如何都要改，因为\(pos\)位置的数和前面的数的所有种类肯定不一样，所以需要让其 +1，并使\(pos + 1\) -> \(n\)的末尾全部清零，使得每次操作n变化的尽可能小，然后再一直用这个方法找到符合条件的n。ps：记得特判\(n_{pos}\) 是否为9，这时候+1就变0并且需要进位。

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<cstring>

using namespace std;

int t, k, vis[15];
string n;
set<char> s;

int main()
{
    cin >> t;
    while(t --)
    {
        s.clear();
        cin >> n >> k;
        for(int i = 0; i < n.size(); i++)
            s.insert(n[i]);
        if(s.size() <= k)
            cout << n << endl;
        else
        {
            int flag = 1;
            while(flag)
            {
                s.clear();
                memset(vis, 0, sizeof vis);
                int pos = 0, cnt = 0;
                for(pos = 0; pos < n.size() && cnt <= k; pos++)
                {
                    int x = n[pos] - ‘0‘;
                    if(!vis[x]) //!!!vis[n[pos] - ‘0‘]会翻车
                    {
                        vis[x] = 1;
                        cnt ++;
                    }
                }
                pos --; //找到第一个使得n有大于k个不同数的位置
                if(n[pos] == ‘9‘) pos --; //特判：该位 = 9，则进1
                n[pos] ++;
                for(int i = pos + 1; i < n.size(); i++) //后面所有位置0
                    n[i] = ‘0‘;
                for(int i = 0; i < n.size(); i++) s.insert(n[i]);
                if(s.size() <= k) flag = 0;
            }
            cout << n << endl;
        }
    }
}

Codeforces Round #739 (Div. 3) F. Nearest Beautiful Number（思维、贪心）

原文：https://www.cnblogs.com/K2MnO4/p/15171876.html