洛谷 P1106 删数问题

题目描述

键盘输入一个高精度的正整数 NN（不超过 250250 位），去掉其中任意 kk 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 NN 和 kk，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

nn（高精度的正整数 )。

kk（需要删除的数字个数 )。

输出格式

最后剩下的最小数。

输入输出样例

输入 #1复制

175438 
4

输出 #1复制

13

分析
当前位数去掉k位后即为新数的位数，从原数高位到低位找新数的每一位即可。不清楚还剩多少位（多少个循环），写成递归形式。

代码

#include<bits/stdc++.h>
using namespace std;

string N;
int K;
int q;//原数的位数
int p;//新数的位数 

string ans="";

void dfs(int position,int step)//每一层都有个回溯值 
{
    if(step>=p) return;
    int min_num=100;//最小值
    int min_position;//记录一下最小值位置，因为下次只能选后面的了 
    for(int i=position;i<q-(p-step/*p减去已经拿了的位数即是没有拿的*/)+1/*加1是因为此时还没有记录层数*/;i++)//防止后面没拿的了 
    {
        if(N[i]-'0'<min_num)//不能写等于，如果都一样要先拿前面，给后续选数留下空间 
        {
            min_num=N[i]-'0';
            min_position=i;
        }
    }
    char mn=min_num+'0';
    ans+=mn;
    dfs(min_position+1,step+1);
}

int main()
{
    cin>>N;
    cin>>K; 
    q=N.length();
    p=N.length()-K;//新数的位数
    dfs(0,0);
    
    int u=ans.length();
    int flag=true;//定义一个flag看0串结束没有 
    for(int i=0;i<u;i++)//本题巨坑点，前几位可以全是是0，自动忽略。之前我还专门特判不能为0…… 
    {
        if(ans[i]=='0'&&flag) continue;
        else
        {
            flag=false;
            cout<<ans[i];
        }
    }
    //特判只有一个0     
    if(u==1&&ans[0]=='0')
    {
        cout<<"0"<<endl;
    }
    cout<<endl;
    return 0;
}