P9766 [ROIR 2021 Day 2] 好数 题解

kaneki_02 · 2023-11-08 09:36:29 · 题解

P9766 [ROIR 2021 Day 2] 好数 题解

思路

先考虑第一类好数，直接从 9 到 1 枚举所有可能的情况满足条件更新答案即可，因为是从大到小枚举的最后更新出来的一定是最优解。

再考虑第二类好数，因为最多只有 20 位，那么直接暴力枚举不变的位数的位置，然后从 0 到 9 枚举变的情况，更新最小答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
long long ans=1e17;
long long k,a[20],given;
long long Min(long long a,long long b){
    return a<b?a:b;
}
int main(){
    cin>>s>>k;
    for(int i=0;i<s.size();i++){
        given*=10;
        given+=s[i]-'0';
    }//记录原数
    if(k==0){
        for(int i=9;i>=1;i--){//从大到小枚举
            long long now=0;
            for(int j=0;j<s.size();j++){
                now*=10;
                now+=i;
            }
            if(now>=given){//更新答案
                ans=now;
            }
        } 
    }else{
        for(int i=0;i<=9;i++){
            for(int j=0;j<=9;j++){
                for(int k=1;k<=s.size();k++){//枚举不变的位置
                    long long now=0;
                    if(i==0&&k==1)continue;//去掉前导0
                    for(int a=1;a<=k-1;a++){
                        now*=10;
                        now+=j;
                    }
                    now*=10;
                    now+=i;
                    for(int a=k+1;a<=s.size();a++){
                        now*=10;
                        now+=j;
                    }
                    if(now>=given)ans=Min(ans,now);//更新答案
                }
            }
        }
    }
    cout<<ans;//输出
    return 0;
}