【3002】删去K个数字

Time Limit: 3 second

Memory Limit: 2 MB

【问题描述】

输入一个数字串S和整数K(K小于数字串S的长度)，从S中删去K个数字，使剩余数字在保持相对位置不变的情况下构成一个值最小的整数。例如：S='19990608'，K=4，处理结果为608。如果串S含有非数字字符，则输出'error'，如果K的值大于串S的长度，则输出'error'。

【输入】

两行，第一行为数字串S，第二行为整数K。

【输出】

一行，处理结果或error

【输入样例】

19990608

4

【输出样例】

【题解】

这是一道贪心题。

先考虑一种比较简单的情况。

123456,接下来删除一个数字。

如果删掉1 就是2 开头了

这显然不是最小的，因为我们可以删掉2，那这个数字就是1开头的了，但删掉2第二位是3，如果删掉3 第二位就是2 这样更优。。。

如此如此可以知道删掉6是最优的情况。

再来复杂点

489456 这里就不能单纯地删掉6了。我们可以把它分成两个部分

489 和 456 如果单纯対这两个数做删除操作我们可以容易地得到答案。

那么问题来了，我们应该删掉9还是删掉6呢？

答案是9，因为如果我们让后者更小，最后结果是489XXX

而如果让前者更小，最后结果则是484XXX，显然让前者更小是更优的解法。

或者你可以把这489和456看成X和Y，然后把这两个数组成一个2位数

最后的结果是X*10+Y,那让X更小显然是更优的解。

如果是484950这个就把 48 和49 和50 看成X,Y,Z显然也是让X最小是最优的解。

就是这样吧。

这里的9和6是两个递增区间的最后一个数字。

while (a[i] <= a[i+1]) i ++ ，这样找到i，然后用erase删掉就好。

不要忘记去除开头可能多余的0；

【代码】

#include <cstdio>

#include <string>

#include <iostream>

#include <stdlib.h>

using namespace std;

string s1;

int n,k;

void s_p()

{

    printf("error");

    exit(0);

}

void input_data()

{

    cin >> s1;

    n = s1.size();

    scanf("%d",&k);

    if (k > n) //如果输入的K不符合要求，则判错

        s_p();

    if (k == n) //

        {

            printf("0");

            exit(0);

        }

}

void get_ans()

{

    for (int i = 0;i < n;i++)

        if (s1[i] < '0' || s1[i] > '9') //如果有非法字符 也判错

            s_p();

    for (int i = 1;i <= k;i++) //删除k个数字

        {

            int j = 0;

            while (s1[j] <= s1[j+1]) j++; //找到第一个递增区间的最后一个数字

            s1 = s1.erase(j,1); //删掉这个数字。

        }

    int m = s1.size();

    int i = 0;

    while (m > 1 && s1[i] == '0') //删掉开头多余的0

        {

            s1 = s1.erase(0,1);

            m--;

        }

}

void output_ans()

{

    cout << s1 << endl;

}

int main()

{

    input_data();

    get_ans();

    output_ans();

    return 0;

}

巴特西