首页 > 试题广场 >

选靓号

[编程题]选靓号
  • 热度指数:5659 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
A 国的手机号码由且仅由 N 位十进制数字(0-9)组成。一个手机号码中有至少 K 位数字相同则被定义为靓号。A 国的手机号可以有前导零,比如 000123456 是一个合法的手机号。
小多想花钱将自己的手机号码修改为一个靓号。修改号码中的一个数字需要花费的金额为新数字与旧数字之间的差值。比如将 1 修改为 6 或 6 修改为 1 都需要花 5 块钱。
给出小多现在的手机号码,问将其修改成一个靓号,最少需要多少钱?

输入描述:
第一行包含2个整数 N、K,分别表示手机号码数字个数以及靓号至少有 K 个数字相同。
第二行包含 N 个字符,每个字符都是一个数字('0'-'9'),数字之间没有任何其他空白符。表示小多的手机号码。
数据范围:
2 <= K <= N <= 10000


输出描述:
第一行包含一个整数,表示修改成一个靓号,最少需要的金额。
第二行包含 N 个数字字符,表示最少花费修改的新手机号。若有多个靓号花费都最少,则输出字典序最小的靓号。
示例1

输入

6 5
787585

输出

4
777577

说明

花费为4的方案有两种:777577与777775,前者字典序更小。
头像 方寸间沧海桑田
发表于 2019-07-27 22:07:59
(1)思路:以0到9为最佳数字n,循环10次,每次循环中寻找当数字为n时达到K个数字相同时的最小代价(首先是代价,其次才是字典序);(2)算法:从数字n开始向外扩散,采用贪心算法思想(代价为先),首先寻找相同的数字,然后寻找比该数字大1与小1的数字,然后是大2与小2的的数字,以此类推,直到到达K个相 展开全文
头像 白色高跟鞋
发表于 2020-04-26 02:35:04
Python30行解决 思路 —— for 0~9 循环找出应当相同的数字为same_number:即对每一位进行abs()计算,排序代价选前K个并求和;记录最小值和此时对应的same_number。(详见代码及其中注释) 因为要满足字典序最小输出,分析可得 —— 数字nums[i]变为same_ 展开全文