51Nod 2499 不降的数字

Problem

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

Solution

从后向前找，每次不满足不降，前面的数就减一，这时候后面的所有数都可以变成9。

Code

//#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define mem(ss) memset(ss,0,sizeof(ss))
typedef long long ll;
typedef long double ld;
typedef __int128 lll;
const ll mod=1e9+7;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//using namespace std;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;}
int n,cnt,a[20];
int main(){
    //io_opt;
    scanf("%d",&n);
    int bf=n;
    while(n){
        a[++cnt]=n%10;
        n/=10;
    }
    for(int i=2;i<=cnt;i++){
        if(a[i]>a[i-1]){
            a[i]--;
            for(int j=i-1;j>=1;j--){
                a[j]=9;
            }
        }
    }
    while(!a[cnt]) cnt--;
    for(int i=cnt;i>=1;i--){
        printf("%d",a[i]);
    }
    return 0;
}