专栏文章

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

zzyxjeek
P12289题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miod2bn5
此快照首次捕获于
2025/12/02 17:13
3 个月前
此快照最后确认于
2025/12/02 17:13
3 个月前
查看原文

题意简述

把一个数字 aa 改成 bb 要花费 ∣b−a∣|b-a|，你要修改一个数 mm，让修改后的数存在连续的 1010 位，包含了从 00 到 99 的所有数字。求最小花费。

思路

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

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...