蓝桥杯2022年第十三届决赛真题-最大数字
时间限制: 2s 内存限制: 320MB 提交: 5703 解决: 1321
题目描述
给定一个正整数 N。你可以对 N 的任意一位数字执行任意次以下 2 种操作：
1. 将该位数字加 1。如果该位数字已经是 9，加 1 之后变成 0。
2. 将该位数字减 1。如果该位数字已经是 0，减 1 之后变成 9。
你现在总共可以执行 1 号操作不超过 A 次，2 号操作不超过 B 次。
请问你最大可以将 N 变成多少？
输入格式
第一行包含 3 个整数：N, A, B。
输出格式
一个整数代表答案。
样例输入复制
123 1 2
样例输出复制
933
提示
对百位数字执行 2 次 2 号操作，对十位数字执行 1 次 1 号操作。
对于 30% 的数据，1 ≤ N ≤ 100; 0 ≤ A, B ≤ 10
对于 100% 的数据，1 ≤ N ≤ 1017; 0 ≤ A, B ≤ 100
1.分析
1.预处理出所有位数所需加和减的次数。
2.dfs找出最大的数。
3.如果加法和减法都无法到9，那么只有加法是可用的。
2.代码
#include<iostream>
using namespace std;
typedef long long LL;
const int MAX = 1110;
string s,t;
int a, b;
int add[MAX], del[MAX];
string re="";
void check(int d,int x) { //预处理
add[d] = 9 - x;
del[d] = x - 0 + 1;
}
void dfs(int d,int x,int y) { //dfs
if (x==0&&y==0) { //判断
if (re<s||re=="") {
re = s;
}
return;
}
for (int i = d; i < s.size(); i++) { //遍历
if (s[i] == '9') continue;
if (x >0) {
if (x > add[i]) { //可以加到9
s[i] = '9';
dfs(i + 1, x - add[i], y);
s[i] = t[i];
}
else { //可以加，但是不能加到9
s[i] = t[i] - '0' + x + '0';
dfs(i + 1, 0, y);
s[i] = t[i];
}
}
if (y >= del[i])
{
s[i] = '9';
dfs(i + 1, x, y - del[i]);
s[i] = t[i];
}
}
if (s > re) { //判断
re = s;
}
}
int main() {
cin >> s >> a >> b;
t = s;
for (int i = 0; i < s.size(); i++) {
check(i, s[i] - '0');
}
dfs(0,a,b);
cout << re << endl;
return 0;
}