【题解-信息学奥赛一本通】1321：【例6.3】删数问题(Noip1994)
题目：1321：【例6.3】删数问题(Noip1994)
题目描述
输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。
输出新的正整数。（n不超过240位）
输入数据均不需判错。
输入
n
s
输出
最后剩下的最小数。
时空限制
1s / 64MB
样例输入
175438 4样例输出
13思路
从前向后遍历，如果当前的数小于前面的数，那么删除前面的数，否则，删除最后一个数。
注意删除前导0。
代码
#include<bits/stdc++.h>usingnamespacestd;constintN=240+10;string s;intn,len,a[N];boolflag;voiddel(intk){for(inti=k+1;i<len;i++)a[i-1]=a[i];len--;}intmain(){cin>>s>>n;len=s.size();for(inti=0;i<s.size();i++){a[i]=s[i]-'0';}while(n--){flag=false;for(inti=1;i<len;i++){if(a[i-1]>a[i]){del(i-1);flag=true;break;}}if(!flag)del(len-1);}while(len>1&&a[0]==0)del(0);for(inti=0;i<len;i++)cout<<a[i];return0;}