试题详情
简答题通过键盘输入一个高精度的正整数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；

  • 关注下方微信公众号，在线模考后查看

热门试题