首页 > 试题广场 >

选靓号

[编程题]选靓号

热度指数：5708 时间限制：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，前者字典序更小。

算法知识视频讲解

Python

ElonB

"""
最小修改距离，
先找最小修改距离ans_cost下，相同的数字ans_num
再求以ans_num为修改目标，当修改值大于ans_num时从前往后修改，
当修改值小于ans_num时从后往前修改
"""
from collections import Counter


def distance(dic, k, t):
    ret = 0
    if dic[t] >= k: return ret
    k -= dic[t]
    for i in range(1, 10):
        if t + i < 10:
            if dic[t + i] >= k:
                ret += i * k
                return ret
            else:
                k -= dic[t + i]
                ret += i * dic[t + i]
        if t - i >= 0:
            if dic[t - i] >= k:
                ret += i * k
                return ret
            else:
                k -= dic[t - i]
                ret += i * dic[t - i]


def modify(s, dic, k, t):
    if dic[t] >= k: return
    k -= dic[t]
    for i in range(1, 10):
        if t + i < 10:
            for j in range(len(s)):
                if k == 0: return
                if s[j] == t + i:
                    s[j] = t
                    k -= 1
        if t - i >= 0:
            for j in range(len(s) - 1, -1, -1):
                if k == 0: return
                if s[j] == t - i:
                    s[j] = t
                    k -= 1


if __name__ == "__main__":
    n, k = map(int, input().strip().split())
    s = list(map(int, list(input().strip())))
    dic = Counter(s)
    for i in range(10):
        if i not in dic:
            dic[i] = 0
    ans_cost, ans_num = float("inf"), -1
    for i in range(10):
        tmp = distance(dic, k, i)
        if ans_cost > tmp:
            ans_cost = tmp
            ans_num = i
    modify(s, dic, k, ans_num)
    print(ans_cost)
    print(''.join(map(str, s)))

发表于 2019-07-17 21:23:53 回复(3)

Python

大佬求带。。

import math
import copy
def repone(a, k, n):
res = copy.deepcopy(a)
cost = 0
p=1
t = 0
while p:
for i in range(len(a)):
if t == n:
break
if a[i]-k == p :
res[i] = k
t += 1
cost +=p
for j in range(len(a)):
if t == n:
break
if k-a[len(a)-j-1] == p :
res[len(a)-j-1] = k
t += 1
cost +=p
p+=1
if t == n:
break
return cost,res
if __name__ == "__main__":
N,K = list(map(int,input().split(" ")))
s = input()
num = list(map(int,list(s)))
w_num = list(sorted(list(set(num))))
res = []
cost = []
for val in w_num:
if num.count(val) >= K:
res = [num]
cost = [0]
break
c,o = repone(num, val, K-num.count(val))
#print(c,o)
res.append(o)
cost.append(c)

index = cost.index(min(cost))
print(cost[index])
ss = list(map(str, res[index]))
print("".join(ss))

发表于 2019-04-28 21:03:03 回复(0)