http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2072.html

删数问题

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic Discuss

Problem Description

键盘输入一个高精度的正整数n（≤100位），去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s，寻找一种方案，使得剩下的数字组成的新数最小。

Input

输入有多组 每组包括原始数n，要去掉的数字数s；

Output

输出去掉s个数后最小的数

Example Input

178543 4

Example Output

13

注意前导0,和输出0的情况重叠

贪心策略：每次删去有高位到低位递增区间的末尾或者递减区间的首位，实现局部贪心

#include <iostream>

#include <string>

#include <cstring>

#include <cstdio>

using namespace std;

void modify(char (&str)[102]) {

    int num = 0;

    while (str[num]=='0')

        num ++;

    int x = 0;

    for (int j = num ; str[j-1]!='\0'; j++) {

        str[x++] = str[j];

    }

}

int main() {

    char arr[102];

    while ((gets(arr) != NULL) && arr[0] != '0') {

        int n,i;

        cin >> n;

        getchar();

        int len = strlen(arr);

        if (n==strlen(arr)) {

            cout << "0" << endl;

            break;

        }

        //数字完全删除的情况

        while (n) {

            i=0;

            while (i<strlen(arr)&&arr[i]<=arr[i+1])

                i++;

            for (int j = i; j<=strlen(arr); j++)

                arr[j]=arr[j+1];

            n--;

        }

        //贪心策略

        if (arr[0]=='0')

            modify(arr);

        //除去前导0

        if (arr[0]=='\0') {

            cout << "0" << endl;

            break;

        }

        //前导0，输出0的情况

        printf("%s\n",arr);

    }

    return 0;

}