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[];

int main()

{

    int n,k,i,j,f=;

    s[]=;

    scanf("%d%d",&n,&k);

    getchar();

    for(i=; i<n; i++)

    {

        char c;

        c=getchar();

        while(c>s[f])

        {

            if(!k||!f)break;

            k--;

            f--;

        }

        s[++f]=c;

    }

    f-=k;

    s[++f]=;

    printf("%s",s+);

    return ;

}

巴特西

TOJ 4493 Remove Digits 贪心

最新文章

热门文章