题解 | #选靓号#

解题思路

这是一道贪心算法问题，主要思路如下：

判断是否已经是靓号：
- 统计每个数字出现的次数
- 如果有数字出现次数 $\geq K$ ，则已经是靓号，无需修改
寻找最优修改方案：
- 枚举每个数字作为目标数字
- 计算将其他数字修改为目标数字的最小花费
- 记录最小花费和对应的修改方案
执行修改：
- 按照记录的方案修改原始号码
- 大于目标数字从左到右修改
- 小于目标数字从右到左修改

代码

cpp
java
python

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 10005;

int main() {
    int n, k;
    char s[MAXN];
    
    while(scanf("%d%d", &n, &k) != EOF) {
        scanf("%s", s);
        int count[10] = {0};
        bool isLucky = false;
        
        // 统计每个数字出现次数
        for(int i = 0; i < n; i++) {
            count[s[i]-'0']++;
            if(count[s[i]-'0'] >= k) {
                isLucky = true;
            }
        }
        
        // 已经是靓号
        if(isLucky) {
            printf("0\n%s\n", s);
            continue;
        }
        
        // 寻找最优修改方案
        int minCost = INF;
        int targetDigit = -1;
        int finalPlan[10] = {0};
        
        for(int i = 0; i <= 9; i++) {
            int needed = k - count[i];
            int tempPlan[10] = {0};
            int cost = 0;
            
            // 计算修改成数字i的花费
            for(int j = 1; j <= 9 && needed > 0; j++) {
                // 检查i+j
                if(i+j <= 9 && count[i+j]) {
                    int change = min(needed, count[i+j]);
                    tempPlan[i+j] = change;
                    cost += j * change;
                    needed -= change;
                }
                // 检查i-j
                if(needed > 0 && i-j >= 0 && count[i-j]) {
                    int change = min(needed, count[i-j]);
                    tempPlan[i-j] = change;
                    cost += j * change;
                    needed -= change;
                }
            }
            
            if(needed == 0 && cost < minCost) {
                minCost = cost;
                targetDigit = i;
                memcpy(finalPlan, tempPlan, sizeof(tempPlan));
            }
        }
        
        // 执行修改
        for(int i = 9; i >= 0; i--) {
            if(i > targetDigit) {
                // 从左到右修改
                for(int j = 0; j < n && finalPlan[i]; j++) {
                    if(s[j]-'0' == i) {
                        s[j] = targetDigit + '0';
                        finalPlan[i]--;
                    }
                }
            } else if(i < targetDigit) {
                // 从右到左修改
                for(int j = n-1; j >= 0 && finalPlan[i]; j--) {
                    if(s[j]-'0' == i) {
                        s[j] = targetDigit + '0';
                        finalPlan[i]--;
                    }
                }
            }
        }
        
        printf("%d\n%s\n", minCost, s);
    }
    return 0;
}

import java.util.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static final int MAXN = 10005;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            String s = sc.next();
            char[] num = s.toCharArray();
            
            // 统计每个数字出现次数
            int[] count = new int[10];
            boolean isLucky = false;
            for(char c : num) {
                count[c-'0']++;
                if(count[c-'0'] >= k) {
                    isLucky = true;
                }
            }
            
            // 已经是靓号
            if(isLucky) {
                System.out.println("0");
                System.out.println(s);
                continue;
            }
            
            // 寻找最优修改方案
            int minCost = INF;
            int targetDigit = -1;
            int[] finalPlan = new int[10];
            
            for(int i = 0; i <= 9; i++) {
                int needed = k - count[i];
                int[] tempPlan = new int[10];
                int cost = 0;
                
                // 计算修改成数字i的花费
                for(int j = 1; j <= 9 && needed > 0; j++) {
                    if(i+j <= 9 && count[i+j] > 0) {
                        int change = Math.min(needed, count[i+j]);
                        tempPlan[i+j] = change;
                        cost += j * change;
                        needed -= change;
                    }
                    if(needed > 0 && i-j >= 0 && count[i-j] > 0) {
                        int change = Math.min(needed, count[i-j]);
                        tempPlan[i-j] = change;
                        cost += j * change;
                        needed -= change;
                    }
                }
                
                if(needed == 0 && cost < minCost) {
                    minCost = cost;
                    targetDigit = i;
                    finalPlan = tempPlan.clone();
                }
            }
            
            // 执行修改
            for(int i = 9; i >= 0; i--) {
                if(i > targetDigit) {
                    for(int j = 0; j < n && finalPlan[i] > 0; j++) {
                        if(num[j]-'0' == i) {
                            num[j] = (char)(targetDigit + '0');
                            finalPlan[i]--;
                        }
                    }
                } else if(i < targetDigit) {
                    for(int j = n-1; j >= 0 && finalPlan[i] > 0; j--) {
                        if(num[j]-'0' == i) {
                            num[j] = (char)(targetDigit + '0');
                            finalPlan[i]--;
                        }
                    }
                }
            }
            
            System.out.println(minCost);
            System.out.println(new String(num));
        }
    }
}

def solve(n, k, s):
    # 统计每个数字出现次数
    count = [0] * 10
    for c in s:
        count[int(c)] += 1
        if count[int(c)] >= k:
            return 0, s
    
    # 寻找最优修改方案
    min_cost = float('inf')
    target_digit = -1
    final_plan = None
    
    for i in range(10):
        needed = k - count[i]
        temp_plan = [0] * 10
        cost = 0
        curr_needed = needed
        
        # 计算修改成数字i的花费
        for j in range(1, 10):
            if curr_needed <= 0:
                break
            # 检查i+j
            if i+j <= 9 and count[i+j]:
                change = min(curr_needed, count[i+j])
                temp_plan[i+j] = change
                cost += j * change
                curr_needed -= change
            # 检查i-j
            if curr_needed > 0 and i-j >= 0 and count[i-j]:
                change = min(curr_needed, count[i-j])
                temp_plan[i-j] = change
                cost += j * change
                curr_needed -= change
        
        if curr_needed == 0 and cost < min_cost:
            min_cost = cost
            target_digit = i
            final_plan = temp_plan[:]
    
    # 执行修改
    num = list(s)
    for i in range(9, -1, -1):
        if i > target_digit:
            # 从左到右修改
            for j in range(n):
                if final_plan[i] > 0 and int(num[j]) == i:
                    num[j] = str(target_digit)
                    final_plan[i] -= 1
        elif i < target_digit:
            # 从右到左修改
            for j in range(n-1, -1, -1):
                if final_plan[i] > 0 and int(num[j]) == i:
                    num[j] = str(target_digit)
                    final_plan[i] -= 1
    
    return min_cost, ''.join(num)

while True:
    try:
        n, k = map(int, input().split())
        s = input().strip()
        cost, result = solve(n, k, s)
        print(cost)
        print(result)
    except EOFError:
        break

算法及复杂度

算法：贪心算法
时间复杂度： $\mathcal{O}(n)$ - $n$ 为号码长度
空间复杂度： $\mathcal{O}(1)$ - 只需要常数空间存储计数和方案