首页 > 代码库 > nyist oj 448 寻找最大数 (基础题)

nyist oj 448 寻找最大数 (基础题)

寻找最大数

时间限制: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
来源
第六届itat复赛B卷2题改编
上传者

ACM_赵铭浩

这道题属于一般的基础题,水题,但是也很容易出错,不仔细理解题意的话,就容易贡献wa,开始我题目意思没搞清楚,就以为是直接删除几位数然后找其中的最大值,就直接用一个排序,按照从大到小的顺序排序,然后输出前m位,恰巧样例也能通过。。然后就贡献了几次wa,后来仔细看了一下题目,是要求删除m个数字之后,按原次序组成的数最大;这个地方处理也有一定的技巧性;

看到有的大神直接是用了动态规划的思想来做(我还是一个DP菜鸟啊。。),这里直接用两个循环嵌套,查找m+1这段区间中的最大值,然后把这个最大值输出,用一个变量标志最大值的这个位置;找到n-m个最大值就行了。

这种处理的思想要掌握,以后再其他地方也会用到这种思想;

下面是代码;代码比较精简:

#include <cstdio>
#include <cstring>
int main()
{
    int t,m,len,max;
    char s[101];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%d",s,&m);
        len=strlen(s);
        for(int i=0,j=0;m<len;m++)//看到有些人这里j赋的是-1;
        {
            max=0;
            while(j<=m)//这里要保证位数
            {
                if(s[j]>max)
                {
                    max=s[j];
                    i=j;//标记最大值的位置
                }
                j++;//向下查找
            }
            j=i+1;
            printf("%c",s[i]);
        }
        printf("\n"); 
    }
    return 0;
}