题目描述

小科同学最近醉心于动态规划的研究，他苦学百年，已经牢牢掌握了最长上升子序列的知识。

小科对于这种单调不减的序列非常着迷，于是他写下了一个数 。

他希望找到最大的一个小于等于 x 的数，使得这个数的各个数位是单调不减的。

他觉得这太简单了，于是想考考你。

输入格式

从文件 increase.in 中读入数据。

一行一个数 。

输出格式

输出到文件 increase.out 中。

一行一个数表示答案。

对于$100\%$的数据,$0\le{x}\le10^{10^5}$

#include<bits/stdc++.h>
using namespace std;
string s,s1;
int main(){
	int p=-1;
	cin>>s;
	s1=s;
	char c=s[0];
	for(int i=1;i<s.size();i++){
		if(c>s[i]){
			if(p==-1) p=i;
			s[i]=c;
		}else{
			c=s[i];
		}
	}
	c=s[s.size()-1];
	for(int i=s.size()-1;i>=p&&p!=-1;i--){
		s[i]='9';
	}
	int flag=0;
	for(int i=p-1;i>=0;i--){
		if(i!=0&&c!=s[i-1]){
			s[i]--;
			break;
		}
		if(i==0){
			flag=1;
		}
	}
	if(flag==1) {
		if(s[0]!='1') cout<<(char)(s[0]-1);
		for(int i=1;i<s.size();i++){
			cout<<s[i];
		}
	}
	else cout<<s;
	return 0;
}

爆0了/悲