南阳题目448-寻找最大数

Bertha 。 2022-07-28 10:57 139阅读 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

来源

[第六届itat复赛B卷2题改编][itat_B_2]

上传者

这个题目意思就是给一串数，不改变次序，要求去除给定的个数的数，让剩下的数最大

我们要用贪心的想法，然后保留最后要留的位数减一位（为啥呢？因为这样我们就可以保证一定能取够要求的位数），从前面的那么多位中选择一个最大的，从这个最大的数的下一位到保留最后要留的位数减两位中，找最大的，依次找下去...

比如

1008908 5

总共7位，要找2位，所以要从除了最后一位的前6位里面找出一位最大的。

然后从选择的那一位的下一位开始，到第七位中找到最大的一个。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int m,n,i,j;
    	char a[1001];
    	scanf("%d",&m);
    	
    	while(m--)
    	{
    		scanf("%s%d",a,&n);
    		int ta,len=strlen(a),ma,f=-1;
    			ta=len-n;
    			while(ta--)
    			{
    				ma=-1;
    				for(i=f+1;i<len-ta;i++)
    				{
    					if(a[i]-'0'>ma)
    					{
    						ma=a[i]-'0';
    						f=i;
    					}
    				}
    				printf("%c",a[f]);
    			}
    		printf("\n");
    	}
    	return 0;
     }

[itat_B_2]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%AC%AC%E5%85%AD%E5%B1%8Aitat%E5%A4%8D%E8%B5%9BB%E5%8D%B72%E9%A2%98%E6%94%B9%E7%BC%96