zzulioj--1828-- 贪心的小猫咪（贪心模拟）

1828: 贪心的小猫咪

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 14  Solved: 4

SubmitStatusWeb Board

Description

“老鼠你们都给我听着！”
对于老鼠来说，一只可爱的小猫咪恍若一个邪恶的撒旦。
“最近我可是越来越无聊了，所以我打算找几只老鼠陪我玩耍，不过呢，我现在给你们一串数字，你们可以减去一位，然后剩下的数字就是要陪我玩的数量！”
不过可爱的小猫咪数学不是很好，所以对于他来说只有1-9的数字，所以他给你的数字不会出现0.
于是老鼠们一起去找老鼠长老商讨，希望能得到最少的数量。

Input

多实例，输入一个数，数字位数小于10^6。

Output

输出最小的数。

Sample Input

123456789

Sample Output

12345678

维护前方最长的单调上升序列

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char s[1000100];
int main()
{
	while(scanf("%s",s)!=EOF)
	{
		int l=strlen(s);
		int i;
		int m=s[0]-'0';
		for(i=1;i<l;i++)
		{
			if(s[i]-'0'>=m)
			{
				m=s[i]-'0';
			}
			else
			{
				s[i-1]='';
				break;
			}
		}
		if(i==l)
		s[l-1]='';
		for(i=0;i<l;i++)
		{
			if(s[i]!='')
			printf("%c",s[i]);
		}
		printf("
");
	}
	return 0;
}