专栏文章

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

RRyan_X
P12289题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miobt4kh
此快照首次捕获于
2025/12/02 16:38
3 个月前
此快照最后确认于
2025/12/02 16:38
3 个月前
查看原文

简述题意

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

大致思路

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

枚举子段

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

求子段最小花费

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

代码实现

CPP
#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;
}
完结撒花~~

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...