Nearest Beautiful Number (hard version)

---

题目

Nearest Beautiful Number (hard version)

---

问题描述

与简单版的区别在于k的范围由原来的$k<=2$拓展到了$1<=k<=10$
由于数据范围的变化，之前的思路就不适用于这里了。

---

分析

思路一（贪心，枚举）

通过set的互异性，来记录x中的数字种数，一旦x中的数字种数小于等于k，就结束操作，返回结果。
先令x等于n，要注意的是，在操作中，我们保证每次操作的结果都会大于原先的x。

具体操作

从第一位开始，我们保证在前缀里面出现的数字种数小于等于k，如果当前这一位放入集合后不会使得总数大于k，就继续处理下一位。

while (true){
    set<char> s;for (auto c : n) s.insert(c);if (s.size() <= k) return n;s.clear();int ptr = 0;for (; ; ptr++){
    s.insert(n[ptr]);if (s.size() > k){
    //......break;}}}

若当前位进入集合后造成种数大于k，那么就对前缀（包括当前位）进行加一操作，对后续置零。

比如当n=1292,k=2时，处理到第三位’9’的时候，结果大于k，就对前缀加一，后续置零，得到1300；
再处理1300，仍然再处理第三位时出现大于k的情况继续加一置零，得到1310（有点枚举的味道了）；
再继续处理1310,处理到第四位时，加一，后续已无法置零，得到1311，满足条件，这就是结果了。

加一：是枚举可能，并且扩大x；

置零：保证扩大后的结果是前缀满足条件的情况下最小的。

这样操作的话，时间复杂度主要跟长度有关，若长度为m，则为$O(m^2)$

代码

#include <bits/stdc++.h>using namespace std;string solve()
{
    string n;int k;cin >> n >> k;while (true){
    set<char> s;for (auto c : n) s.insert(c);if (s.size() <= k) return n;s.clear();int ptr = 0;for (; ; ptr++){
    s.insert(n[ptr]);if (s.size() > k){
    while (n[ptr] == '9')ptr--;n[ptr]++;for (int i = ptr + 1; i < n.size(); i++)n[i] = '0';break;}}}
}int main()
{
    int t;cin >> t;while (t--)cout << solve() <<endl;return 0;
}

---

思路二（DFS）

具体操作

区别于上面记录种数的方法，这里记录数字种数是通过二进制上面1的个数来记录.

设参数为mask，当我们向mask里面放入数字5时，可以通过mask|(1<<5) 放入5，若存在，由于或运算不会影响；若不存在，就置该位为1；
同时有一个函数__$builtin$_$popcount()$可以直接求出二进制中1的个数，很方便。

解释一下代码中一些参数的作用：

全局变量ans：标记有无结果产生，使用前要先置零。
dfs参数lim：标记是否可以沿用原数据的值作为当前循环的起点，初始为1，过程中，在调整的时候置零，表示要从0开始依次搜索。
dfs参数pos：搜索所处的位数，初始为1，当pos为len+1时，说明前len个已经有了答案。此时可以返回结果，结束循环。
dfs参数mask：以二进制来记录当前已经加入的数字种数。
dfs参数sum：记录结果，也就是前缀的值。

仍然以n=1292，k=2为例，把过程走一遍，
处理第一位1时，mask变为$(10{)}_2$，计数的值小于等于2，进入下一层；

处理第二位2时，mask变为$(110{)}_2$,计数结果仍然小于等于2，进入下一层；

处理第三位9时，mask变为$(1000000110{)}_2$,计数结果为三，大于2，返回上一层；

此时处于第二位，要对2的下一位3进行搜索，此时mask变为$(1010{)}_2$，计数结果小于等于2，同时lim要置为0，表示对下一层从0开始搜索；

第三层，0会使种数大于2，测试到1时，mask为$(1010{)}_2$，满足条件，下一层，仍然以lim为0开始搜索，所以这个的时间复杂度不会太理想。

最后得到结果1311.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[12];
int len,ans,k;
int cal(int mask)//计算二进制有多少个1
{
    return  __builtin_popcount(mask);
}
void dfs(int lim,int pos,int mask,int sum)
{
    if(pos==len+1){
    ans=sum;return ;}int start=0;if(lim){
    start=s[pos];}for(int i=start;i<=9;i++){
    if(ans==0&&cal(mask|(1<<i))<=k){
    dfs(lim&&i==start,pos+1,mask|(1<<i),sum*10+i);}}
}
int main()
{
    int t;int n;cin>>t;while(t--){
    scanf("%s",s+1);cin>>k;len=strlen(s+1);for(int i=1;i<=len;i++){
    s[i]-='0';}ans=0;dfs(1,1,0,0);cout<<ans<<endl;}return 0;
}

---

思路三（map+贪心）

具体操作

再次区别上方记录种数的方法，这里还可以使用map键值对来记录，而且map会进行自动排序，方便后续从中进行选择。

	map<char, int> d;int pref = 0;while (pref < n.length())//计算原来的数字种数 {
    if (d.count(n[pref])){
    d[n[pref++]]++;continue;}if (d.size() == k) break;d[n[pref++]]++;}

依旧以n=1292，k=2为例，把过程走一遍，

先进行一次循环，计算数字种数的同时，若满足条件会返回结果，但结束循环时并没有满足条件，还需要往下进行，此时可以得知是在第二位使得跳出循环，且此时pref指向了第三位，map刚好有两组键值对。

第三位恰为9，所以需要处理这一位的上一位，将其对map的影响从map中抹除，可能是把值减一，也可能是删除那组键值对，此时对应的是删除。

保证了pref所对应的位数不是9后，若经过删除使得键值对恰好为k-1（删除恰好改变了键值对数目，而且之前为k，此时若改变只会为k-1），此时pref所处位进行加一操作并再次加入map中，再从map中选出最小值（不会影响k）对后续进行填充，若仍然满足k-1，则可以取更小的0来填充。
从而此时就已经得到了结果1311。

当然了，若采用另外的数据，删除之后map依旧满足等于k，则需要从map找出第一个大于当前值的键值对，若找到，用其来填充后续，满足最小的条件；
若找不到，删除上一位的影响，继续循环。

代码

#include <bits/stdc++.h>using namespace std;string solveFillingSuffix(string& n, char d, int from)//从from开始，将n中后续都置为d 
{
    for (int i = from; i < n.length(); i++)n[i] = d;return n;
}void decAt(map<char, int>& d, char c)//抹除c对map的影响 
{
    if (d.count(c)){
    d[c]--;if (d[c] == 0) d.erase(c);}
}string solve()
{
    string n;int k;cin >> n >> k;map<char, int> d;int pref = 0;while (pref < n.length())//计算原来的数字种数 {
    if (d.count(n[pref])){
    d[n[pref++]]++;continue;}if (d.size() == k) break;d[n[pref++]]++;}if (pref == n.length())//成功遍历，没有触发break，种数小于等于k return n;while (true){
    if (n[pref] == '9'){
    decAt(d, n[--pref]);continue;}if (d.size() < k)//返回结果 {
    d[++n[pref]]++;return solveFillingSuffix(n, d.size() < k ? '0' : d.begin()->first, pref + 1);}auto it = d.upper_bound(n[pref]);//从map里面找出第一个大于当前位的值 if (it == d.end())//如果没找到 {
    decAt(d, n[--pref]);continue;}n[pref] = it->first;return solveFillingSuffix(n, d.begin()->first, pref + 1);//返回结果 }
}int main()
{
    int t;cin >> t;while (t--)cout << solve() << '\n';return 0;
}