P1106 删数问题

展开

题目描述

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

输入格式

nn (高精度的正整数)

kk(需要删除的数字个数)

输出格式

最后剩下的最小数。

输入输出样例

输入 #1复制

175438

4

输出 #1复制

13

思路：从前往后枚举，删除上升子串的最后一位。也就是如果s[i]>s[i+1]，那么就删除s[i];
由于删除操作比较麻烦，可以采用第i+1到n位向前移一位的方式。
还要考虑前导0的问题。

#include<iostream>

#include<string>

using namespace std;

int main()

{

    string s;

    int k;

    cin >> s;

    cin >> k;

    int k1=k;

    int q;

    while(k--)

    {

        int flag=;

        for(int i=; i<s.size(); i++)

        {

            if(s[i]>s[i+])

            {

                q=i;

                flag=;

                break;

            }

        }

        if(flag)

        {

            for(int i=q; i<s.size(); i++)

            {

                s[i]=s[i+];

            }

        }

    }

    int num=;

    while(num<s.size()-k1&&s[num]=='')

        num++;

    if(num==s.size()-k1)

        cout <<  << endl;

    else

    {

        for(int i=num;i<s.size()-k1;i++)

            cout << s[i];

        cout << endl;

    }

    return ;

}

巴特西

P1106 删数问题

题目描述

输入格式

输出格式

输入输出样例

最新文章

热门文章