P370【基础】删数问题 题解

本文主要是介绍P370【基础】删数问题 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意

键盘输入一个高精度的正整数n（n<=1000位），去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。

编程对给定的n和s（s<n的位数，且数据保证n删除s个数之后不为0，还是一个非0的整数），寻找一种方案，使得剩下的数字组成的数最小。

例如：153748要删除2个数，使得剩下的数字最小，应当删除5和7，得到1348。（注意：1087如果要删除1个数，删除1结果是最小的，得到结果87）

输入格式

第一行是一个高精度整数n

第二行是需要删除的位数s

输出格式

最后剩下的最小数

样例输入

 153748
 2

样例输出

 1348

题解

运用贪心算法

如果要从153748中取出1个数，使这个数最小，应该取5

如果要从13748中取出1个数，使这个数最小，应该取7

假设不是取两个数，我们再从1348中取出1个数，使这个数最小，应该取8

可以发现：1，5是一个不降序数列（有相等的升序），也就是逐渐变多，而5，3是一个不升序数列（有相等的降序），逐渐减少。

5正好是升序数列的最后一个，也是降序数列的第一个。(其他同理)

只需要找到第一个升序数列的末尾并取出它就可以算成功完成了“局部的最优解”，再通过这个继续取出更多的数，直到取出s个数来，从局部的最优解进阶到全局的最优解，这一道题就完成了！

TIPS:如果是一个纯升序序列，需要特判，只需从末尾取出相应个数即可最小

代码

#include <bits/stdc++.h>
using namespace std;

string s;
int r;
int main()
{
 
 cin >> s >> r;
 
 bool flag = 0;  //判断是否是纯升序序列
 int time = 0;	//记录操作次数
 for(int i = 0; ; i++)
 {
 	if(time == r) break;  //如果已经取了r次，退出循环
 	if(s[i] <= s[i + 1]) continue;  //如果升序，继续往后扫描
 	else 
 	{
 		flag = 1;
 		s.erase(s.begin() + i);   //否则取出这位（删除操作）
 		i = -1,time++;   // i变为-1，下次循环i++后i变为0从头开始再次扫描
 	}
 }
 
 if(flag == 0) 	//如果是纯升序，删除最后r位
 {
 	for(int i = 0; i < s.size() - r; i++)
 		cout << s[i];	
 }
 else 
 {
 	int pos = 0;
 	for(int i = 0; i < s.size(); i++)   //这个操作是为了去除“前导0”
 		if(s[0] == '0' && s[i] == '0' && s[i + 1] != '0')
 		{
 			pos = i + 1;
 			break;
 		}	 
 		
 	for(int i = pos; i < s.size(); i++)
 		cout << s[i];
 }
 	
 return 0;
} 

这篇关于P370【基础】删数问题 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！