TOJ 4493 Remove Digits贪心

题目

4493: Remove Digits

Description

Given an N-digit number, you should remove K digits and make the new integer as large as possible.

Input

The first line has two integers N and K (N不大于500000). The next line has a N-digit number with no leading zero.

Output

Output the largest possible integers by removing K digits.

Sample Input 4 2 2835 Sample Output 85

在一个字符串里找到n-k位的递减数列or前几位递减，一直超时。。。

#include <stdio.h> char s[500005]; int main() {int n,k,i,j,f=0; s[0]=9; scanf("%d%d",&n,&k); getchar(); for(i=0;i<n;i++){ char c; c=getchar(); while(c>s[f]){ if(!k||!f)break; k--;f--;} s[++f]=c; } f-=k; s[++f]=0; printf("%s",s+1); return 0; }