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

· · 题解

简述题意

给定一个字符串，要通过修改操作让字符串中至少出现一段长度为十且恰好包含 0 到 9 所有数字的子段，求最小花费。

大致思路

我们可以枚举每一个长度为十的子段，再对于当前子段求出最小花费，最后统计出所有子段中最小的花费。

枚举子段

我们可以用单调队列来枚举，每次把过期的队头弹出，把当前数位压入队尾，维护一个数组来记录当前队列中所有数值出现的次数。

求子段最小花费

每次检查队列元素个数，如果大于等于 10 个，则需要求最小花费。从小到大遍历每一个数值，分别用两个数组存储缺少的数值和多出的数值。不难发现，这两个数组的大小是一样的。所以可以使用贪心的思想，把多出的小数值修改为缺少的小数值，把多出的大数值修改为缺少的大数值，这样一定就是最小的花费。如果当前子段的最小花费小于当前记录的最小花费，则更新我们的最小花费。

最后输出最小花费即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
int num[100],s[20],d[20];
deque<int>q;
int main(){
    string n;
    cin>>n;
    int siz = n.size();
    n = " "+n;
    long long ans = LONG_LONG_MAX;
    for(int i = 1;i<=siz;i++){
        while(!q.empty() && q.front()+10-1<i){
            num[n[q.front()]-'0']--;
            q.pop_front();
        }
        q.push_back(i);
        num[n[i]-'0']++;
        if(i>=10){
            int tot = 0;
            memset(d,0,sizeof(d));
            memset(s,0,sizeof(s));
            for(int j = 0;j<=9;j++){
                if(num[j]>1){
                    for(int k = 1;k<=num[j]-1;k++)d[++tot] = j;
                }
            }
            tot = 0;
            for(int j = 0;j<=9;j++){
                if(num[j] == 0){
                    s[++tot]+=j;
                }
            }
            long long sum = 0;
            for(int j = 1;j<=tot;j++)sum+=abs(d[j]-s[j]);
            ans = min(ans,sum);         
        }
    }
    cout<<ans;
    return 0;
}

完结撒花~~