UVA11491 奖品的价值

奖品的价值C804

运行时间限制：1000ms； 运行空间限制：51200KB

试题描述

你是一个电视节目的获奖嘉宾。主持人在黑板上写出一个 n 位非负整数（不以 0 开头），邀请你删除其中的 d 个数字，剩下的整数便是你所得到的奖品的价值。当然，你希望这个奖品价值尽量大。1<=d<=n<=10^5

输入

两行，第一行仅包含一个正整数d，第二行位一个符合题目要求的 n 位数。

输出

一个数，未奖品价值的最大值。

输入示例

4 23987921

输出示例

9921

很像万恶的小奥。。。（小时候都看过这题吧）

挺简单的，贪心

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int n,d,k;//k代表当前删除了几个数

char a[];

int main()

{

    while(scanf("%d%d",&n,&d) && n && d)//n是串长，d是删除数字个数

    {

        getchar();

        k=;

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

        {

            char c=getchar();

            while(k> && k+(n-i)>n-d && a[k]<c)//剩下的多了，删除比c小的

                k--;

            if(k<n-d) a[++k]=c;//剩下的少了，加入c

        }

        a[++k]='\0';

        puts(a+);

    }

    return ;

}

喜欢就给个推荐呗