洛谷-P1106-删数问题

  • A+

删数问题 - 洛谷


解题思路:

1.由题可知,输入一个不超过250位的非负整数,超出了 long long的范围,所以可以利用字符串来输入数字, 并利用一个整型的数组从下标1开始来存储最高位到最 低位的数字

2. 首先考虑,在一个n位的整数中去掉k个数字,然后形 成新的数字,要求这个数字最小,那么其实就是在n位 中选取n-k个数字,并且是按照原来的次序要求这个数 最小,那么就可以利用到贪心的思想

3. 如果这个数最小,那么最高位上一定是最小的数,所 以我们第一遍可以遍历有可能取的第一位,然后在这 些数里,选取最小的那个数作为首位,把他存放到另 一个结果数组中,然后接着取第二位,方法一致

4. 可能这里会有疑问,为什么每一位取出来的数字是规 定范围的,举个例子,如果一个8位的整数,去掉2 位,结果为6位数字,那么,如果取第一位的话,他只 能在前三位上取,因为要保证新数字的长度为n-k,比 如67486327,因为形成的数字还是按照原来的次序 的,所以为了保证有6位,第一位只能在6,7,4中选择, 很明显,第一位应该选4,4后面剩下5个数字,为了保 证结果是6位数,那么只能剩下的数字依次还是原来 的,即结果为486327

5. 如果这个数字是67886327,第一位应该是选择6,那么 第二个要取的数字只能在7,8,8中选择,因为总要保证 结果为n-k位,所以每个取得数字是有规定的范围的

6.那么如何确定每个数字的选择范围呢,可以设置一个 书签int temp=1,因为第一个数字如果占用的遍历长度 长,而且选择的最小数的位置编号大,那么后面的选 择会变小,所以他们是共用的一段长度,简单手动模 拟,第一个数他的选择范围为[1,1+k],即temp+k,当 确定好第一个最小数的位置编号为j时,它所用的长度 为res=res+j-temp,res为已经用了的长度,然后第二个数 从j的下一个位置开始遍历temp=j+1,可以选择的范围 就是[temp,temp+(k-res)],重复以上步骤,一共取 ans次

7.那for循环里的内容就是选择最小的那个数字,然后添 加到结果数组中,一共取n-k次

8. 最后去除前导0,利用打标记的方法,如果结果都为 0,那么输出0


#include<bits/stdc++.h>
using namespace std;
int shu[300],jieguo[300];
int main()
{
    string a;
    cin>>a;//输入字符串 
    int len=a.length();//计算字符串的长度 
    int k;
    cin>>k;
    int num=0;
    for(int i=0;i<len;i++)
    shu[++num]=a[i]-'0';//将字符串数字转化到数组中,并从下标1开始 
    int temp=1,ans=len-k,x=0;//temp为书签,ans为要取的数字个数,x为下标 
    int res=0;//前面数字用了的长度 

    while(ans--)//一共要取ans次数 
    {
        int min=11,j;
        for(int i=temp;i<=temp+k-res;i++)
        {
            if(shu[i]<min)
            {
                min=shu[i];//判断最小数 
                j=i;//记录最小数的编号 
            }
        }

        res+=j-temp;//累加长度 
        jieguo[x]=shu[j];//最小数存到结果数组中 
        x++;
        temp=j+1;//书签移动到j下一个位置 
    }
     
    bool flag=0;//去除前导0 
    for(int i=0;i<x;i++)
    {
        if(jieguo[i]!=0)
        flag=1;

        if(flag==1)
        cout<<jieguo[i];
    }

    if(flag==0)//进行特判 
    cout<<0;
    return 0;
}

w3cjava

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: