不降的数字

2499 不降的数字

1. 2 秒
 
2. 262,144 KB
 
3. 10 分
 
4. 2 级题

 

小b有一个非负整数 N，她想请你找出 ≤N≤N 的最大整数x，满足x各个位数上的数字是不降的。也就是说，设x的十进制表示为 a1,a2,…,ama1,a2,…,am，则对于任意 1≤i<m1≤i<m，ai≤ai+1ai≤ai+1。

 收起

 

输入

输入一个非负整数N。
0≤N≤10^9

输出

输出一个整数，表示答案

输入样例

332

输出样例

299
思路：从后往前扫描如果不符合降序则前一位减一，后面的贪心全变成9

#include<Iostream>
using namespace std;
int aa[15];
int main(){
    string a;
    cin>>a;
    int la=a.size();
    for(int i=0;i<la;i++){
        aa[i+1]=a[i]-48;
    }
    for(int i=la;i>1;i--){
        if(aa[i]<aa[i-1]){
            aa[i-1]--;
            for(int j=i;j<=la;j++)
            aa[j]=9;
        }
    }
    int sum=0;
    for(int i=1;i<=la;i++)
    sum=sum*10+aa[i];
    cout<<sum<<endl;
    return 0;
}