题目

https://www.luogu.com.cn/problem/P12289

思路

思路还是比较好想的，枚举所有区间进行择优即可。

可以使用滑动窗口优化，就不必重复读入。

注意多余的数字，多余多少，就要添加多少，而不是只添加一次。

Code

枚举

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;

const int N = 1000010;
int cnt[10];

int main()
{
    string s;
    cin >> s;

    int res = 2e9;
    for(int i = 0; i+9 < s.size(); i ++)
    {
        //对于每一个长度为10的区间
        memset(cnt, 0, sizeof(cnt));
        for(int j = i; j < i+10; j ++)
            cnt[s[j]-'0']++;

        vector<int> lose,have;
        //找出多余的数字、缺失的数字
        for(int j = 0; j < 10; j ++)
        {
            if(cnt[j] > 1) //多余
            {
                int k = cnt[j]-1;
                while(k--)//这里注意多余几个就要加入几个！
                    have.push_back(j);
            }
            else if(cnt[j] == 0)//缺失
                lose.push_back(j);
        }//按照这样遍历，得到的数组是升序的

        int sum = 0;
        for(int j = 0; j < have.size(); j ++)
            sum += abs(have[j]-lose[j]);

        res = min(res,sum);
    }
    cout << res << endl;
    return 0;
}

滑动窗口小优化

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;

const int N = 1000010;
int cnt[10];

int main()
{
    string s;
    cin >> s;

    int res = 2e9;
    //滑动窗口初始化
    for(int i = 0; i < 10; i ++) //先存储前10个字符
        cnt[s[i]-'0']++;

    for(int i = 9; i < s.size(); i ++)//i代表窗口右端点
    {
        vector<int> lose,have;
        //找出多余的数字、缺失的数字
        for(int j = 0; j < 10; j ++)
        {
            if(cnt[j] > 1) //多余
            {
                int k = cnt[j]-1;
                while(k--)//这里注意多余几个就要加入几个！
                    have.push_back(j);
            }
            else if(cnt[j] == 0)//缺失
                lose.push_back(j);
        }//按照这样遍历，得到的数组是升序的

        int sum = 0;
        for(int j = 0; j < have.size(); j ++)
            sum += abs(have[j]-lose[j]);

        res = min(res,sum);

        //移动到下一个窗口位置
        if(i+1 >= s.size()) //最后一个窗口，跳出
            break;
        cnt[s[i-9]-'0']--;//窗口左端元素滑出
        cnt[s[i+1]-'0']++;//下一个元素进入窗口
    }
    cout << res << endl;
    return 0;
}