首页 > 试题广场 >

选靓号

[编程题]选靓号

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

算法知识视频讲解

Java

何止hz

24 ms

9476K

整体思路为改成0-9看看花费是多少，对于改成 i 优先满足把比 i 大的改成 i ，这样可以满足改成 i 的内部字典序最小。对于花费相同的，比较两者字典序。

在修改成 i 的过程中，比 i 大的从前往后修改，比 i 小的从后往前修改。

我个人觉得逻辑还是比较复杂的。这是修改后的代码，原代码有bug但由于测试用例太少也通过了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

/**
 * @Author: coderjjp
 * @Date: 2020-05-08 10:18
 * @Description: 选靓号
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int N = Integer.valueOf(s[0]);
        int K = Integer.valueOf(s[1]);
        char nums[] = br.readLine().toCharArray();//原始号码
        int hash[] = new int[10];//存储每个数字有几个
        for (int i = 0; i < N; i++)
            hash[nums[i]-'0']++;
        int cost = Integer.MAX_VALUE;//记录最小花费
        HashMap<Integer, int[]> changed_nums = new HashMap<>();
        //K:存储修改至哪个数字，V:存储被修改的数字及数量,即用map记录最小花费的情况有哪些
        for (int i = 0; i <=9 ; i++ ){
            int diff = K - hash[i];
            int cur_cost = 0;
            int cur_changed_num[] = new int[10];
            for (int d = 1; d <=9 && diff > 0 ; d++){
                if (i + d <= 9){//优先将大的修改至i
                    int pd = hash[i+d];
                    if (pd >= diff){
                        cur_changed_num[i+d] = diff;
                        diff=0;
                    }else {
                        cur_changed_num[i+d] = pd;
                        diff -= pd;
                    }
                    cur_cost += cur_changed_num[i+d]*d;
                }
                if (i - d >= 0){//再将小的修改至i
                    int pd = hash[i-d];
                    if (pd >= diff){
                        cur_changed_num[i-d] = diff;
                        diff=0;
                    }else {
                        cur_changed_num[i-d] = pd;
                        diff -= pd;
                    }
                    cur_cost += cur_changed_num[i-d]*d;
                }
            }
            if (cur_cost < cost){//如果当前花费比之前的最小花费少
                changed_nums.clear();//将之前的情况清空
                changed_nums.put(i, cur_changed_num);//将当前情况记录下来
                cost = cur_cost;
            }
            if (cur_cost == cost)//如果当前花费与之前的最小花费相同
                changed_nums.put(i, cur_changed_num);
            //如果当前花费比之前的最小花费少，直接跳过即可
        }
        System.out.println(cost);
        String ans = Character.toString((char)('9'+1));
        for (int c: changed_nums.keySet()) {
            String cur_ans = getGMN(nums, N, c, changed_nums.get(c));
            if (cur_ans.compareTo(ans) < 0)
                ans = cur_ans;
        }
        System.out.println(ans);
    }

    private static String getGMN(char[] nums, int N, int c, int[] changed_num){
        StringBuilder sb = new StringBuilder();
        for (char cs : nums)
            sb.append(cs);
        for (int i = 0; i < N; i++){
            if (nums[i]-'0' > c && changed_num[nums[i]-'0'] > 0){//比i大的从前往后修改
                changed_num[nums[i]-'0']--;
                sb.setCharAt(i, (char)('0'+c));
            }
        }
        for (int i = N-1; i >= 0; i--){//比i小的从后往前修改
            if (nums[i]-'0' < c && changed_num[nums[i]-'0'] > 0){
                changed_num[nums[i]-'0']--;
                sb.setCharAt(i, (char)('0'+c));
            }
        }
        return sb.toString();
    }
}

编辑于 2020-05-08 14:36:23 回复(0)