蓝桥杯2022年第十三届决赛真题-最大数字

解题思路:

位数相同的数字大小关系取决于不同最高位的大小有关,所以我们可以先找从最高位到低位最多有多少位可以变成9

观察数据发现数字n最多是1E17,也就是17位用dfs不会超时

对于剩余的A和B操作次数

B:可以遍历剩余的位数看看是否能将某一位变成9(高位优先)
A:直接在剩余位数的最高位加上剩余的A操作次数就好

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int a,b;
}x[105];
int ans=0;
int numa=0;
int numb=0;
string n;
void dfs(int i,int a,int b)
{
	if(i==n.length()||(x[i].a>a&&x[i].b>b))
	{
		if(ans<i)
		{
			ans=i;
			numa=a;
			numb=b;
		}
		else if(ans==i)
		{
			numa=max(numa,a);
			numb=max(numb,b);
		}
		return;
	}
	if(x[i].a<=a)
	{
		dfs(i+1,a-x[i].a,b);
	}
	if(x[i].b<=b)
	{
		dfs(i+1,a,b-x[i].b);
	}
}
int main()
{
	
	int a,b;
	cin>>n>>a>>b;
	for(int i=0;i<n.length();i++)
	{
		x[i].a='9'-n[i];
		x[i].b=((n[i]-'0')+1)%10;
		//cout<<x[i].b;
	}
	dfs(0,a,b);
	for(int i=0;i<ans;i++)
	{
		n[i]='9';
	}
	for(int i=ans;i<n.length();i++)
	{
		if(x[i].b<=numb)
		{
			numb-=x[i].b;
			n[i]='9';
		}
	}
	for(int i=ans;i<n.length();i++)
	{
		if(x[i].a>numa)
		{
			n[i]+=numa;
			break;
		}
	}
	cout<<n;
	return 0;
}