当前位置:首页 > 贪心 > 正文
NOI4.6-3528最小新整数
4011+

题目大意:一个十亿以内的整数,删掉m位后,得到一个新的整数,这个整数最小是多少?

题目描述

给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。

现在从m位中删除k位(0<k < m),求生成的新整数最小为多少?

例如: n = 9128456, k = 2, 则生成的新整数最小为12456

输入

第一行t, 表示有t组数据;

接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。

输出

t行,每行一个数字,表示从n中删除k位后得到的最小整数。

样例输入

2
9128456 2
1444 3

样例输出

12456
1

解题思路

要整数最小,那么最高位要最小,次高位要在此基础上再最小……因此,我们可以先确定最高位的数,在确定次高位的,这样一直下去,知道整个数确定为止。

一个数字有n位,删除m位,也就是保留n-m位。

先把问题转换成n位数字删除m位。把数字读入到字符串s,找最高位(第1位)的时候,右边必须保证有m-1个数字,留给后面的低位,那么第一位可以找的范围是s[0]到s[n-(m-1)-1]。那么,下一个高位在哪里找?s[1]到s[n-(m-2)-1]吗?不是的!因为如果前一位已经找到3了,那么这一位只能从4开始找到n-(m-2)-1。所以,程序中用k表示所找区域的左边界,找到最小那个数字s[k]后,将他输出,然后k+1,表示下次从k+1开始找下一个最高位。

程序实现

About

坚决不Copy代码!

本文标签:,

NOI4.6-3528最小新整数:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!