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

1828: 贪心的小猫咪

Time Limit: 1 Sec Memory Limit:
128 MB

Submit: 14 Solved: 4

Submit Status Web
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]='\0';

				break;

			}

		}

		if(i==l)

		s[l-1]='\0';

		for(i=0;i<l;i++)

		{

			if(s[i]!='\0')

			printf("%c",s[i]);

		}

		printf("\n");

	}

	return 0;

}

巴特西