简答题

通过键盘输入一个高精度的正整数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;

答案解析

相似试题
  • 如图所示是滑道压力测试的示意图,光滑圆弧轨道与光滑斜面相切,滑道底部B处安装一个压力传感器,其示数N表示该处所受压力的大小,某滑块从斜面上不同高度h处由静止下滑,通过B时,下列表述正确的有()。

    单选题查看答案

  • 一个氢原子从n=3能级跃迁到n=2能级,该氢原子()。

    单选题查看答案

  • 请用悬念导入法给“等比数列前n项和”这节课设计一个课堂导入。

    简答题查看答案

  • 已知一个线性储存的线性表设每个结点需要占n个存储单元,若第一个结点地址为xul,则第i个结点的地址为()。

    单选题查看答案

  • 已知非齐次递归方程:其中,b、c是常数,g(n)是n的某一个函数。则f(n)的非递归表达式为:现有Hanoi塔问题的递归方程为:,求h(n)的非递归表达式。

    简答题查看答案

  • 如图所示,两个相同的空心金属球壳M和N,M带-Q电荷,N不带电,旁边各放一个不带电的金属球P和R(M、N相距很远,互不影响),当将带正电Q的小球分别放入M和N的空腔时()

    单选题查看答案

  • 某工厂生产A、B、C三种不同型号的产品,产品数量之比依次为2:3:5。现用分层抽样方法抽出一个容量为n的样本,样本中A种型号产品有16件。求此样本的容量n。

    简答题查看答案

  • Word2003中,若键盘上的CapsLock灯亮,输入小写字母要用到()键。

    单选题查看答案

  • 设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:  ①每个选手必须与其他n-1名选手比赛各一次;  ②每个选手一天至多只能赛一次;  ③循环赛要在最短时间内完成。  (1)如果n=2k,循环赛最少需要进行几天;  (2)当n=23=8时,请画出循环赛日程表。

    简答题查看答案