寻找最大数--nyoj题目448

小咪咪 2022-08-04 08:56 177阅读 0赞

## 寻找最大数 ##

时间限制： 1000 ms | 内存限制：65535 KB

难度： 2

描述

请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大，

比如当n=92081346718538，m=10时，则新的最大数是9888

输入

第一行输入一个正整数T，表示有T组测试数据  
每组测试数据占一行，每行有两个数n,m（n可能是一个很大的整数，但其位数不超过100位，并且保证数据首位非0，m小于整数n的位数）

输出

每组测试数据的输出占一行，输出剩余的数字按原次序组成的最大新数

样例输入

2
    92081346718538 10
    1008908 5

样例输出

9888
    98
    
    
    
    
    
    
    这个题开始的时候想着用排序，后来觉得不合适，排完序后都乱了
    
    后来开了学长代码才知道用贪心算法，这里要注意去掉数的次数是怎么来控制的

1 #include<cstdio>
     2 #include<cstring>
     3 #include<algorithm>
     4 using namespace std;
     5 
     6 int main()
     7 {
     8     int N,i,m,len,id;
     9     char str[104],ch;
    10     scanf("%d",&N);
    11     while(N--)
    12     {
    13         scanf("%s %d",str,&m);
    14         len=strlen(str);
    15         id=0;//用来标记当前最大数的位置
    16         while(m<len)
    17         {
    18             
    19             for(i=id;i<=m;i++)//这里先从0-m中找出最大数，然后铺把当前id标记为最大数id，m+1，最后的效果就是比较了len-m次每次找出一个最大数！
    20             {
    21                 ch=str[id];
    22                 if(ch<str[i])
    23                 id=i;//更新当前最大数id
    24             }
    25             printf("%c",str[id]);
    26             id++;//从最大数下一个数开始比
    27             m++;//主要由m控制比较的次数
    28         }
    29         printf("\n");
    30     }
    31     return 0;
    32  }