Nearest Beautiful Number (easy version)

题目

Nearest Beautiful Number (easy version)

问题描述

给定数据$n(1\le n\le 10^9)$跟$k(k\le 2)$
$x$由不超过$k$种数字所组成，输出满足$x\ge n$中最接近$n$的$x$。

例：$n=177890,k=2$
输出$x=181111$

分析

思路一（先枚举再二分）

由于数据的范围，所以有一个取巧的办法，先在set1里面存入k为1的数据，也就9个；再在set2里面存入满足k为2的数据（由一个数字或两个数字组成），通过循环可以依次枚举出来。
最后输入n跟k后，只需要在对应的集合里面用函数二分查找出大于等于n的第一个数，就是满足条件的x。

思路二（循环模拟）

当k等于1时，只需要从大到小枚举字符串，输出第一个大于等于n的字符串，转为字符串后字符串比较的规则与数的大小比较规则是一致的；
而且有个规律：从n中取出前t位，与x中的前t位仍然满足条件。

当k等于2时，由于数据不大，此时可以通过模拟来找出第一个符合条件的x：

给定$a$跟$b$，满足$a<b$，先假设可以通过$a,b$构建出满足条件的x，而且为了找到第一个，$a,b$的枚举是从小到大枚举的，所以接下来的目标变为了找到第一个满足$x>=n$且只需要用两种数字表示的$x$。

for(char a = '0'; a <= '8'; a++)for (char b = a + 1; b <= '9'; b++){
    //......}

确定了$a,b$之后，要看是否可以由$a,b$构建出满足条件的x，接下来的循环是由n的第一位开始，直至结束。

处理第$i$位的数据时，我们保证由$a$，$b$构建的$x$的前$i?1$位数据大于等于$n$的前$i?1$位数据，

若第$i$位大于$a$跟$b$，说明这一搭配是不合理的，退出，测试下一组$a,b$；

若第$i$位小于等于$b$，说明这一位可以使用$a,b$来替代，由于$a$更小，为了满足题目要求最接近的最小值，我们优先测试$a$，若大于$a$，再选择$b$,此时由$a$，$b$构建的$x$的前$i$位数据大于等于$n$的前$i$位数据， 再测试第$i+1$位

当我们找到了一组$a,b$可以完全表示出每一位都满足条件的$x$时，这个$x$就是我们的答案，可以返回结果了。

代码

#include <bits/stdc++.h>using namespace std;string solve1(string n)
{
    string res(n.length(), '9');for (char c = '8'; c >= '0'; c--){
    string t(n.length(), c);if (t >= n)res = t;}return res;
}string solve2(string n)
{
    string res(n.length(), '9');for(char a = '0'; a <= '8'; a++)for (char b = a; b <= '9'; b++){
    bool n_ok = true;for (int i = 0; i < n.length(); i++){
    if (n[i] < b){
    string t = n;if (t[i] < a) t[i] = a;else t[i] = b;for (int j = i + 1; j < n.length(); j++)t[j] = a;if (res > t)res = t;}if(n[i] != a && n[i] != b){
    n_ok = false;break;}}if (n_ok) return n;}return res;
}string solve()
{
    string n;int k;cin >> n >> k;if (k == 1) return solve1(n);else return solve2(n);
}int main()
{
    int t;cin >> t;while (t--)cout << solve() << '\n';return 0;
}