nyoj寻找最大数

浅浅的花香味﹌ 2022-05-12 15:18 220阅读 0赞

## 寻找最大数 ##

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

难度：2

输入

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

输出

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

样例输入

2
    92081346718538 10
    1008908 5

样例输出

9888
    98

描述

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

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

这道题目自己也是栽了很多次，首先是智商不够用，题目的意思理解错了，还在想能不能钻一些的空子，后面的全部错误，我才认识到并不是我想的那么简单，最后用了一天的时间终于想懂了。所以还是需要好好学习，不然题目都看不懂。废话不多说。

# 思路： #

首先记住一句话，不能改变原来的顺序，所以匹配，排序的什么统统行不通。例如： 92081346718538   10 .这个数，去掉十个数之后，按原来的次序组成最大数，那么开始计算，一共14位数，如果去掉十位数，剩四位数，要想这四位数最大，那么逐次查找，使得首位最大才是结果最大的前提：一：从前11位开始查找，(为什么不能是12位，例如最大的在12位，那么你怎么输出四位数，因为后面一共就是三位数啊！)，所以找到一位最大数，对这个位置做个标记flag；二，从flag到第12位数，（因为如果在flag之前，那么第一位数就不是第一了，当然最大就不满足了）找到最大值，再做标记flag，依次循环就可以。

#include<cstdio>
    #include <string.h>
    int main() {
    	int N;
    	scanf("%d",&N);
    	while(N--){
    		char num[105];
    		int m;
    		scanf("%s%d",num,&m);
    		int flag = 0;
    		int arr = strlen(num) - m;
    		char max;
    		while(arr--){
    			max = num[flag];
    			for(int i = flag ; i <=m; i++){
    				if(num[i] > max){
    					max = num[i];
    					flag = i;
    				}
    			}
    				printf("%c",max);
    				flag++;
    				m++;
    			}
     			printf("\n");
    		}
    	return 0;
    }