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

· · 题解

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

不得不说，这就是一道类似滑动窗口的贪心题。

首先，我们要知道，如果在一个长度为 10 的一个窗口中，缺少的数字和多余的数字的个数是一样的，举个例子：

1 3 4 6 6 7 8 9 0 8

在这个区间中，缺少的数是 2 和 5，而多余的数是 6 和 8，正好数量相等。

所以，我们可以使用 cnt_i 来存储这个区间中 i 这个数字的出现次数，于是缺少的数字的 cnt_i = 0，而多余的数字的 cnt_i > 2。

我们还要知道，不管你用那个多余的数字变成缺少的数字，最终结果都是一样的，因为差值和不变。

所以只需要顺序统计在 n 中连续出现的所有长度为 10 的区间的答案的最小值即可。

代码如下咩：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+101;
string a;
int t[N];
int cnt[31];
int main(){
    cin>>a;
    int n=a.length();
    if(n<10){
        printf("0");
        return 0;
    }
    for(int i=0;i<n;i++){
        t[i+1]=a[i]-'0';
    }
    int sum=0;
    int ans=0x3f3f3f3f;
    for(int i=1;i<=10;i++){
        if(cnt[t[i]]==0){
            sum++;
        }
        cnt[t[i]]++;
    }
    for(int i=1;i+9<=n;i++){
        if(sum==10){
            printf("0");
            return 0;
        }
        queue<int>ms;
        queue<int>m_;
        for(int j=0;j<=9;j++){
            if(cnt[j]>1){
                for(int k=1;k<cnt[j];k++){
                    ms.push(j);
                }
            }
            if(cnt[j]==0){
                m_.push(j);
            }
        }
        int nowsum=0;
        while(!ms.empty()){
            nowsum+=abs(ms.front()-m_.front());
            ms.pop();
            m_.pop();
        }
        ans=min(nowsum,ans);
        cnt[t[i]]--;
        cnt[t[i+10]]++;
    }
    printf("%d",ans);
    return 0;
}