删数(delete.pas/c/cpp)

用的方法比较奇怪，码量小，主要是贪心不太熟练

【问题描述】

给出一个 N 位数,从中移除 K 个数字,使得剩下的数字组成的数(一个 N-K 位数)的值最大。

【输入格式】

第一行包括两个数字 N,K。
第二行一个 N 位数。

【输出格式】

一行包括一个(N-K)位数,这个数的值最大。

【输入输出样例】

输入
4 2
1924
输出
94

输入
7 3
1231234
输出
3234

输入
10 4
4177252841
输出
775841

【数据说明】

对于 50%的数据,N≤1000。
对于 100%的数据,1≤K<N≤500000。

在我对着题目发了一个小时呆后，想到了一个非常简单的思路：

拿第三个样例来解释一下：我需要寻找6个数字，在找第1个数字的时候，只能从第1个找到第5个（因为至少要给后面留5个数字，最后才能组成一个6位的数字）取最大的那一个，把它标记为last，而下一个就只能从last的后面一个开始循环，一直到第（k+i）个（k为删去数字个数，i为当前搜索的位数）

解释一下k+i是怎么得到的，我们知道（n-k）就是留下的数字个数，而已经找了i个，所以就要留下（n-k-i）个数字，而我们能循环的范围，就是（n-（n-k-i）），化简一下就是（k+i）；

然后就一个个寻找就是了

说一下我犯的2个小错误：

• maxn的值需要初始化为-1，不然遇到0的话就会过滤过去
• 需要加一个当maxn的值到9时就不必再搜的优化

下面附上代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,num=0,a[10],b[10],cc[500050],ss=0,mm=0,maxn=0,aa,last=0;
char z;
int main(){
    freopen("delete.in","r",stdin);
    freopen("delete.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>z;
        cc[i]=z-'0';
    }
    for(int i=1;i<=n-k;i++){
        int maxn=-1;
        for(int j=last+1;j<=k+i;j++){
            if(cc[j]>maxn)last=j;
            maxn=max(maxn,cc[j]);
            if(maxn==9)break;
        }
        cout<<cc[last];
    }
    return 0;
}