题目大意
给你一个n，求最多包含k个不同数字且大于等于n的最小的数。
解题思路
我们想要符合条件的数字尽量小，可以想到的一个暴力方法就是不断的让n加1，直到符合条件为止，观察最后得到的数，不难发现其结果要么是等于原数，要么是前面某一位比n大，然后后面全是k个不同数字中最小的数，所以我们可以不考虑后面那些最小的数，就看前几位怎么搞能得到解。
题目要求用k个不相同的数字，我们就从有k+1个不相同的数字的前缀开始+1，不考虑后面的数字放多少(最后肯定放k个数字中最小的数)，不断的循环，直到得到一个数的是由k个不同的数字形成的前缀+后面若干个0为止，后面0的位置全放k个数中最小的数即可。由于每次进位之后后面的位置就不考虑了，所以顶多就加100次左右。
const int maxn = 2e5+10;
const int maxm = 2e7+10;
int calc(int x) {
int cnt = 0;
ll res = 0;
while(x) {
res |= (1<<(x%10));
x /= 10;
}
while(res) {
res -= res&-res;
++cnt;
}
return cnt;
}
int main() {
IOS;
int __; cin >> __;
while(__--) {
ll n, k; cin >> n >> k;
while(calc(n)>k) {
ll f = n, t = 1;
while(calc(f/10)>k) {
f /= 10;
t *= 10;
} ;
++f;
n = f*t;
}
cout << n << endl;
}
return 0;
}
f1写的十分丑陋的分类讨论
const int maxn = 1e5+10;
const int maxm = 1e6+10;
int main() {
IOS;
int __; cin >> __;
while(__--) {
string n; int k;
cin >> n >> k;
char a = n[0];
string ans;
ans = 'a';
for (char b = '0'; b<='9'; ++b) {
string t;
int f = 0;
if (k==1) a = b;
char ch1 = max(a, b);
char ch2 = min(a, b);
for (int i = 0; i<n.size() && f>=0; ++i) {
char ch = n[i];
if (f==1) t += ch2;
else if (i+1<n.size() && n[i+1]>ch1) {
if (ch2>n[i]) {
t += ch2;
f = 1;
}
else if (ch1>n[i]) {
t += ch1;
f = 1;
}
else f = -1;
}
else if (i+1<n.size() && n[i+1]==ch1) {
bool ok = 0;
for (int j = i+1; j<n.size(); ++j) {
if (n[j]<ch1) break;
if (n[j]>ch1) {
ok = 1;
break;
}
}
if (!ok) {
if (ch2>n[i]) {
t += ch2;
f = 1;
}
else if (ch2==n[i]) t += ch2;
else if (ch1>n[i]) {
t += ch1;
f = 1;
}
else if (ch1==n[i]) t += ch1;
else f = -1;
}
else {
if (ch2>n[i]) {
t += ch2;
f = 1;
}
else if (ch1>n[i]) {
t += ch1;
f = 1;
}
else f = -1;
}
}
else if (ch2>n[i]) {
t += ch2;
f = 1;
}
else if (ch2==n[i]) t += ch2;
else if (ch1>n[i]) {
t += ch1;
f = 1;
}
else if (ch1==n[i]) t += ch1;
else f = -1;
}
if (f!=-1) ans = min(ans, t);
}
cout << ans << endl;
}
return 0;
}