题解：P12289 [蓝桥杯 2024 国 Java A] 修改数位

zyxjeek · 2025-08-13 10:22:38 · 题解

题意简述

把一个数字 a 改成 b 要花费 |b-a|，你要修改一个数 m，让修改后的数存在连续的 10 位，包含了从 0 到 9 的所有数字。求最小花费。

思路

令 a_i 为 m 从左到右第 i 位，可以用滑动窗口维护 a_i, a_{i+1}, \dots, a_{i+9} 这 10 位中数字 j (0 \le j < 10) 的个数，记为 cnt_{i, j}。开两个动态数组 v1, v2。如果 cnt_{i, j}=1，无需操作；如果 cnt_{i, j} = 0，说明需要新增一个数字 j，则在 v1 中添加 j；如果 cnt_{i, j} > 1，说明数字 j 过多了，则在 v2 中添加 cnt_{i, j}-1 个数字 j。容易发现 v1 和 v2 的大小一定相等。由于顺序枚举，v1 和 v2 也都是有序的。我们让 v2[k] 变为 v1[k]，统计花费即为答案。

时间复杂度 \mathcal O(nk)，其中 k = 10。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int cnt[10];
string a;
vector<int> v1, v2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> a;
    a = " " + a;
    int n = a.size()-1;
    for (int i = 1; i <= 10; i++)
        cnt[a[i]-'0']++;
    for (int i = 0; i <= 9; i++) {
        if (cnt[i] == 0) v1.push_back(i);
        else if (cnt[i] > 1) fill_n(back_inserter(v2), cnt[i]-1, i); // 在v2末尾插入cnt[i]-1个i
    }
    int sum = 0;
    for (int i = 0; i < v1.size(); i++)
        sum += abs(v1[i]-v2[i]);
    int ans = sum;
    for (int i = 11; i <= n; i++) {
        v1.clear(); v2.clear();
        cnt[a[i-10]-'0']--, cnt[a[i]-'0']++;
        for (int j = 0; j <= 9; j++) {
            if (cnt[j] == 0) v1.push_back(j);
            else if (cnt[j] > 1) fill_n(back_inserter(v2), cnt[j]-1, j); // 在v2末尾插入cnt[j]-1个j
        }
        sum = 0;
        for (int j = 0; j < v1.size(); j++)
            sum += abs(v1[j]-v2[j]);
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}