本文主要是介绍P1106删数问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
键盘输入一个高精度的正整数 N（不超过 250 位），去掉其中任意 k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 N 和 k，寻找一种方案使得剩下的数字组成的新数最小。
输入格式
输入两行正整数。
第一行输入一个高精度的正整数 n。
第二行输入一个正整数 k，表示需要删除的数字个数。
输出格式
输出一个整数，最后剩下的最小数。
输入输出样例
样例输入
175438 4
样例输出
13
要想数越小,那每一次删除的改变就要尽量大,要想更大,要怎么办呢
就拿样例来举例
先是175438
删哪个数好呢,经过比较是删掉8
剩下的是17543
删哪个好?删7
删完7,这个数变成了1543
接着删,删5
变成143
再删,删4,变成13,得到最终结果
那这是不停地删最大值吗?不是
看看这个例子
14386 1
删一个,如果是删最大值的话,得到的结果就是1436,但其实还有更优的,删4,得1386
那是要什么呢,答案是删除第一个比前面大的数
#include<bits/stdc++.h>
using namespace std;
string s;
int x;
const int N=2e4;
int a[N];
signed main(){cin>>s;cin>>x;if(x>=s.length()){printf("0");return 0;}int len=s.length();for(int i=0;i<len;i++)a[i+1]=s[i]-'0';int head=1;while(x--){for(int i=1;i<len;i++){if(a[i]>a[i+1]){for(int j=i;j<len;j++)a[j]=a[j+1];break;}}len--;}if(len==1&&a[1]==0){//特判printf("0");return 0;}while(!a[head])head++;string l;for(int i=head;i<=len;i++)l.push_back(char(a[i]+'0'));cout<<l;
}这时候就有人问了,比如说要删掉的数在最后一个,这里只遍历1到 len-1,怎么办,看for循环之后的代码:len--
当1到 len-1都没有结果是直接执行len--,删掉最后一个,因为删前面的都不能得到最优解
这篇关于P1106删数问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
