计科余定成

用户名：dotcpp0598358

访问量：15777

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

求具有abcd=(ab+cd)2性质的四位数
浏览：73

[NOIP2004]合并果子
浏览：89

家谱(并查集做法）
浏览：76

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

蓝桥杯2022年第十三届决赛真题-最大数字（搜索+贪心）

　　作者: 计科余定成　　　　发表时间：2023-03-18 13:39:32 浏览：465　|　评论：0　

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

#### 解题思路
贪心：
1. 如果能变成9，则变成9；
1. 如果不能就尽量变大；

注意：因为变成9的方法有两种，但是无法确定哪一种是最优的，所以我们直接暴力搜索，枚举出最大值；

参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
string s;  // 输入的字符串
int a, b;  // 可以执行1号操作的次数a，可以执行2号操作的次数b
int n[25], len;  // 将字符串中的数字按位存储到数组n中，len表示数组长度
vector<string>ans;  // 存储枚举出的所有可行方案
void dfs(int k) {
	if (k > len) {  // 递归终止条件，将当前得到的方案存入ans
		string str;
		for (int i = 1; i <= len; i++) str.push_back(n[i] + '0');
		ans.push_back(str);
		return;
	}
	int x = n[k];  // 记录原来的数值
	int y = a;  // 记录原来的剩余操作次数a
	// 对于1号操作，如果当前数值不是9，则将该位数值变为9，如果可以继续操作，则向后枚举；否则回溯回来。
	if (a >= 9 - n[k]) {
		a -= 9 - n[k];
		n[k] = 9;
		dfs(k + 1);
		n[k] = x;
		a += 9 - n[k];
	} else {
		n[k] += a;
		a = 0;
		dfs(k + 1);
		a = y;
		n[k] = x;
	}
	// 对于2号操作，如果当前数值不是0，则将该位数值变为0，如果可以继续操作，则向后枚举；否则回溯回来。
	if (b >= n[k] + 1) {
		b -= n[k] + 1;
		n[k] = 9;
		dfs(k + 1);
		n[k] = x;
		b += n[k] + 1;
	} else {
		if (a >= 9 - n[k]) {  // 如果不能继续执行2号操作，则转为执行1号操作
			a -= 9 - n[k];
			n[k] = 9;
			dfs(k + 1);
			n[k] = x;
			a += 9 - n[k];
		} else {  // 否则向后枚举
			n[k] += a;
			a = 0;
			dfs(k + 1);
			a = y;
			n[k] = x;
		}
	}
}
int main() {
	cin >> s >> a >> b;
	len = s.size();
	for (int i = 1; i <= len; i++) n[i] = s[i - 1] - '0';
	dfs(1);
	cout << *max_element(ans.begin(), ans.end());  // 输出所有可行方案中的最大值
	return 0;
}
```

无注释版：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
string s;
int a, b;
int n[25], len;
vector<string>ans;
void dfs(int k) {
	if (k > len) {
		string str;
		for (int i = 1; i <= len; i++) str.push_back(n[i] + '0');
		ans.push_back(str);
		return;
	}
	int x = n[k];
	int y = a;
	if (a >= 9 - n[k]) {
		a -= 9 - n[k];
		n[k] = 9;
		dfs(k + 1);
		n[k] = x;
		a += 9 - n[k];
	} else {
		n[k] += a;
		a = 0;
		dfs(k + 1);
		a = y;
		n[k] = x;
	}
	if (b >= n[k] + 1) {
		b -= n[k] + 1;
		n[k] = 9;
		dfs(k + 1);
		n[k] = x;
		b += n[k] + 1;
	} else {
		if (a >= 9 - n[k]) {
			a -= 9 - n[k];
			n[k] = 9;
			dfs(k + 1);
			n[k] = x;
			a += 9 - n[k];
		} else {
			n[k] += a;
			a = 0;
			dfs(k + 1);
			a = y;
			n[k] = x;
		}
	}
}
int main() {
	cin >> s >> a >> b;
	len = s.size();
	for (int i = 1; i <= len; i++) n[i] = s[i - 1] - '0';
	dfs(1);
	cout << *max_element(ans.begin(), ans.end());
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

时间转换（Java代码）

【密码】（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

蓝桥杯2022年第十三届决赛真题-最大数字（搜索+贪心）

评论区

精彩推荐

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

川哥的吩咐（C++代码）

P1002 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （Java代码）

WU-链表数据求和操作（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

计科余定成

TA的其他文章

你可能喜欢

时间转换 （Java代码）

【密码】 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

蓝桥杯2022年第十三届决赛真题-最大数字（搜索+贪心）

评论区

精彩推荐

数组输出 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

川哥的吩咐 （C++代码）

P1002 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （Java代码）

WU-链表数据求和操作 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

时间转换（Java代码）

【密码】（C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

　　评论区

数组输出（C语言代码）

川哥的吩咐（C++代码）

WU-链表数据求和操作（C++代码）