P1106 删数问题题解

题目

键盘输入一个高精度的正整数N（不超过250位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的N和k，寻找一种方案使得剩下的数字组成的新数最小。

输入输出格式

输入格式

输入两行正整数。

第一行输入一个高精度的正整数n。

第二行输入一个正整数k，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

输入输出样例

输入样例

175438 
4

输出样例

13

解析

首先，先举一个例子：1 7 5 4 3 8，删的个数：4

不难看出：第一次删的应该是7，第二次删的应该是5，第三次删的应该是4，第四次删的应该是8

那么，剩下的数就是13。

是如何得出规律的呢？ 我们仔细观察一下这个例子：

第一次删的数为7，和5比较，发现7更大，第二次删的数为5，和4比较，发现5更大

第三次删的数为4，和3比较，发现4更大，第四次删的数为8，和最后一个数比较，发现8更大（如果没有最后一个数，就假设为0）

很明显，就是删去下坡数，也就是这个例子中的7（比5大）、5（比4大）、4（比3大）、8（比最后一个大（假设有，并为0））。

#include<iostream>
#include<algorithm>
using namespace std;
string s;
int n,a[251],l,k;
int main(){
	cin>>s>>n;//扫描进来字符串
	l=s.size();
    for(int i=0;i<l;i++){//将字符拆转化为数字，放入数组中
    	a[i]=s[i]-'0';
	}	
	for(int i=1;i<=n;i++){//循环删去数字的个数
		for(int j=0;j<l;j++){
			if(a[j]>a[j+1]){//删去下坡数字
				for(int k=j;k<l;k++){
					a[k]=a[k+1];
				}
				l--;//长度减1
				break;
			}
		}
	}
	int i=0;
	while(a[i]==0&&k<l-1){//将前导零删除
		k++;
		i++;
	}
	for(int i=k;i<l;i++){
		cout<<a[i];
	}
	return 0;
}