洛谷P1106 删数问题

题目描述

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

输出应包括所去掉的数字的位置和组成的新的整数。（N不超过250位） 输入数据均不需判错。

输入输出格式

输入格式：

n (高精度的正整数)

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

输出格式：

最后剩下的最小数。

输入输出样例

输入样例#1：

175438

4

输出样例#1：

13
分析：贪心思想，我们每次删数肯定是要找前面的大数给删掉，并且这一位还要比下一位大，这样删掉以后一定会变小，模拟k次过程就好了，不过有几点要注意：1.可能会出现前导0.  2.如果删掉只剩下一个数，并且这个数是0，就不能把它当做前导0.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <string>

using namespace std;

string s;

int k,cnt;

bool flag = false;

int main()

{

    cin >> s;

    int sizee = s.size();

    scanf("%d",&k);

    for (int i = ; i <= k; i++)

    {

        for (int j = ; j < sizee - ; j++)

        {

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

            {

                for (int k = j + ; k < sizee; k++)

                s[k - ] = s[k];

                break;

            }

        }

        sizee--;

    }

    for (int i = ; i < sizee; i++)

    if (s[i] != '' || (s[i] == '' && flag) || sizee == )

    {

    cout << s[i];

    if (s[i] != '')

    flag = ;

    }

    return ;

}