SDUT 贪心算法删数问题

Problem Description

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

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

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

178543 4
Example Output

13
Hint

Author

代码：

#include <stdio.h>
#include <string.h>
int main()
{
    char n[101];    //将输入的数字存储为字符串形式
    int s,len,i;    //s：删去的数字数   len：输入数字的长度   i:计数变量
    while(~scanf("%s %d",n,&s))    //获取原始数字和将要删除的数字
    {
    while(s>0)       //s=0时，删数结束。while循环执行逐个删数
    {
        i = 0;          //从i=0开始遍历，寻找第一个递减数列。
        len = strlen(n);      //储存n的位数
        while(i<len&&n[i]<=n[i+1])   //当i<len并且n[i]<=n[i+1]时，不构成递减数列，i++
            i++;
        while(i<len)      //构成递减数列时，删除n[i],之后字符依次前移
        {
         n[i]=n[i+1];
         i++;
        }          //i=len-1时，字符迁移完毕。
        s--;           //继续删除数字
    }
//删除数字结束后，即s=0时
//有时会出现以下情况，删除过程中有可能会使原来包含零的数字串变成若干个以0开始的序列，如80056，第一次删除8后，变成0056，高位的0是无效的，程序中应该处理掉。
        i=0;
        len = strlen(n);
        while(n[i]=='0'&&i<len)    //从i=0开始遍历，直到不为0的那一位
            i++;
        if(i==len)                //如果i=len时还没有出现不为零的位，则该数为零。
            printf("0
");
        else                       //找到不为0的那一位，当作首位，输出。
        {
            for(i=i;i<len;i++)
                printf("%c",n[i]);
            printf("
");
        }

    }
    return 0;

}

小知识
原来，在C语言中没有专门的字符串变量，通常用一个字符数组来存放一个字符串。字符串总是以''作为串的结束符。因此当把一个字符串存入一个数组时，也把结束符 ''存入数组，并以此作为该字符串是否结束的标志。有了''标志后，就不必再用字符数组的长度来判断字符串的长度了。

SDUT 贪心算法 删数问题

SDUT 贪心算法删数问题