自动搬运

查看原文

来自洛谷，原作者为

	Ryan_X 由于本人是 xxs，数学学的不多，还请多多谅解。

搬运于2025-08-24 23:14:22，当前版本为作者最后更新于2025-08-15 10:27:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简述题意

给定一个字符串，要通过修改操作让字符串中至少出现一段长度为十且恰好包含 $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;
}

完结撒花~~