P1106 【删数问题】

GK_PRC · 2023-04-24 12:20:19 · 个人记录

P1106 删数问题

贪心策略：越靠前的山峰越早删除。

s[i] >= s[i-1] && s[i] > s[i+1]

图示

还需要注意:

1、前导0本身就不用输出，所以不能让它占用删除次数。

s[i] >= s[i-1] && s[i] > s[i+1] && s[i] != '0'

2、如果删完后剩下的全是0，要特别处理一下，如：10000 1。

        if(pos==len-1){//10000 1
            cout<<0;
            return 0;
        } 

小技巧：

1、手动在s前后添加'0'，可以不用考虑边界。

2、特判：全删即k==s.size()时，直接输出0，程序结束。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;

string s;
int k, len;

void del(int pos){
    for(int i=pos;i<=len-2;i++)
        s[i]=s[i+1];
    len--;
}

int main(){
    cin>>s>>k;
    if(k==s.size()){
        cout<<0;
        return 0;
    }
    s = '0' + s + '0';//去边界 
    len=s.size();
    while(k--){
        for(int i=1;i<=len-2;i++){
            /*前导0不用输出，所以不能让它占用删除次数*/
            if(s[i]>=s[i-1] && s[i]>s[i+1] && s[i]!='0'){
                del(i);
                break;
            }
        }
    }
    int pos=1;
    while(s[pos]=='0'){
        pos++;
        if(pos==len-1){//10000 1
            cout<<0;
            return 0;
        } 
    } 
    for(int i=pos;i<=len-2;i++)
        cout<<s[i];
    return 0; 
}