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

发表于 阅读次数：

题意简述

把一个数字 \(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\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}

The End