通过键盘输入一个高精度的正整数n（n的有效位数≤240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。 【样例输入】 178543 S=4 【样例输出】 13
正确答案:
为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。
具体算法如下：
输入s，n；
while（s>0）
{i=1； //从串首开始找
while（i
{i++；}
delete（n，i，1）； //删除字符串n的第i个字符
s--；
}
while（length（n）>1）&&（n[1]=‘0’）
delete（n，1，1）； //删去串首可能产生的无用零
输出n；
具体算法如下：
输入s，n；
while（s>0）
{i=1； //从串首开始找
while（i
{i++；}
delete（n，i，1）； //删除字符串n的第i个字符
s--；
}
while（length（n）>1）&&（n[1]=‘0’）
delete（n，1，1）； //删去串首可能产生的无用零
输出n；
答案解析:有
微信扫一扫手机做题