贪心、动态规划之删数问题2072

- 日理万妓 2022-06-09 01:11 287阅读 0赞

### 删数问题 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

178543  4

#### Example Output ####

#### 集训老师讲的时候做的可明白了，几天没敲代码，忘得差不多了，今天做的时候一直wa，原来没考虑最后输出应注意的问题，万一最后删除之后剩下000，则输出0（最后要把字符串以数的形式输出） ####

**思路：1：因为输入的高精度的整数小于100位，所以以字符串的形式输入。**

**2： 从 第一个元素开始，凡是增序就删除。**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main()
    {
        char s[102];
        memset(s,0,sizeof(s));
        int m;
        while(scanf("%s %d",s,&m) !=EOF)
        {  int i,j,k;
            int n = strlen(s);
            for(i = 0;i<=m-1;i++)
            {  n = strlen(s);
               for(j = 0;j<=n-1;j++)
               {
                   if(s[j]>s[j+1])
                   {
                       for(k = j;k<=n-1;k++)
                        s[k] = s[k+1];
                        break;
                   }
               }
            }
            n = strlen(s);
             i = 0;
            while(i<n&&s[i]=='0')
              i++;
            if(i<n)
            {
                while(i<n)
                {
                    printf("%c",s[i]);
                    i++;
                }
            }
            else
                printf("0");
    
            printf("\n");
    
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2187/pid/2072.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2187/pid/2072.html