[数据结构与算法]3245. 找数

3245. 找数

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T,caseNum=0;
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		int len=s.length(),flag=0;
		for(int i=0;i<len-1;++i){
			while(s[i]>s[i+1]){
				s[i]=s[i]-1;          //前面非下降数s[i]不可能为0，否则前面全是0
				for(int j=i+1;j<len;++j)
					s[j]='9';
				if(i>0)--i;          //-1后退位检查是否前一位还符合非下降数
				flag=1;
			}
			if(flag==1)break;
		}
		printf("case #%d:\n",caseNum++);
		cout<<s.substr(s.find('0')+1)<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main(){
	int T,caseNum=0;
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		s='0'+s;
		int len=s.length(),flag=0;
		for(int i=0;i<len-1;++i){
			if(s[i]>s[i+1]){   //第一次出现下降，要比这个数小，则至少此位数-1，若后面某位数-1则还是下降数
				for(int j=i;j>0;j--){
					if(s[j]-1>=s[j-1]){   //找到第一个大于前一位数+1，直接定位到最后-1的位置，防止-1后还是下降数
						s[j]=s[j]-1;
						for(int k=j+1;k<len;++k)  //尽可能大则后面全是9
							s[k]='9';
						break;
					}
				}
				flag=1;
				break;
			}
			if(flag==1)break;
		}
		printf("case #%d:\n",caseNum++);
		cout<<s.substr(s.find_first_not_of('0'))<<endl;  //找到第一个不是0的地方开始复制过去
	}
	return 0;
}