题解：CF2203B Beautiful Numbers

DX3906_ourstar · 2026-03-07 17:28:09 · 题解

发现只有 F(x)<10 时，x 满足条件；于是考虑贪心地减小 x 的数位和，直到其数位和小于 10。

显然对于非最高位，我们把它置 0 最优；对于最高位，把它置 1 最优。同时为了使步数最小，我们会从大到小地考虑非最高位。

于是分两种情况：修改最高位和不修改最高位。对于两种情况，按上述方式求出答案，然后取最小的即可。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;

int T;
int x;

inline int f(int x){
    int res=0;
    while(x)res+=x%10,x/=10;
    return res;
}

inline void work(){
    cin>>x;if(f(x)<10)return cout<<0<<"\n",void();
    vector<int>a;//存储拆出来的数位
    int tmp=x;
    int sum=0;while(tmp)a.push_back(tmp%10),sum+=tmp%10,tmp/=10;
    reverse(a.begin(),a.end());
    sort(a.begin()+1,a.end(),[](int a,int b){return a>b;});
    int res1=0;bool f=0;//不修改最高位的情况
    int rsum=sum;
    for(int i=1;i<a.size();++i){
        if(rsum<10)break ;
        ++res1,rsum-=a[i];
    }
    int res2=1;rsum=sum,rsum-=a[0],++rsum;//修改最高位的情况
    for(int i=1;i<a.size();++i){
        if(rsum<10)break ;
        ++res2,rsum-=a[i];
    }
    return cout<<min(res1,res2)<<"\n",void();          
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>T;while(T--)work();
    return 0;
}