第一题：神奇宝贝大军

1.题目

输入描述
输入第一行包含一个整数n表示神奇宝贝的个数
输入第二行n个不同的整数，表示神奇宝贝的力量
输出描述
输出一个整数表示军队可以取得的最大力量
样式输入
7
1 2 5 4 3 6 7
样式输出
9
样式解析
构造军队的方式为5 3 7，军队力量为5-3+7=9

2.问题分析与算法设计思路

类似地将皮卡丘的战斗力与标号的关系看作函数：

a

=

f

(

b

)

a=f(b)

a=f(b)。则我们只需遍历一次这些皮卡丘，同时过程中挑出所有的极大值和极小值，然后将这些皮卡丘作为军队，即可取得最大军队力量。

为什么这样可以得到最大的军队力量？自己举几个例子就能发现，不取极值点的情况，总可以用取了极值点的情况来替代同时获得更大的军队力量。

或者，你可以发现军队力量将来自函数曲线的下降阶段。若从前往后每两只神奇宝贝为一组，则每一组都相当于在曲线上截取一段；截取的下降落差越大，则军队的力量越大。而前面介绍的神奇宝贝挑选方法，将覆盖曲线上所有的下降阶段。（如果曲线右端是上翘的，可以等效为最后再加一只战斗力为 0 的神奇宝贝）

3.算法实现

1）更新版本

1-更新介绍

记住我们的目标是：尽可能截取函数的下降阶段。

主要改变了极大值和极小值的判定方式：

• 极大值：对于$a[i]$
• 极小值：对于$a[i]$

这样判断极值点更加清晰明确

对于端点单独考虑：

• 左端点：若$a[i]>a[i+1]$
• 右端点：若$a[i]>a[i-1]$

程序过程：

1. 输入神奇宝贝数组
2. 遍历数组，对每个点进行分类（非极值点、极大值点、极小值点）
3. 遍历过程中，每找到一个极小值（在这之前一定也找到了一个极大值），更新一次军队总战斗力：
   $总战斗力+=极大值-极小值$

2-版本代码

#include<iostream>using namespace std;const int Big = 100;//神奇宝贝最大数量 int amy(int bkm[], int n){	int sum = 0;//总战斗力	int max = 0;//极大值	int min = 0;//极小值 		//左端点 	if(bkm[0] > bkm[1]){		max = bkm[0];	}	//中间部分 	for(int i = 1; i <= n-2; i++){		bool found_min = false;//本次循环是否找到极小值 		if(bkm[i] > bkm[i-1] && bkm[i] > bkm[i+1]){			max = bkm[i];		}		else if(bkm[i] < bkm[i-1] && bkm[i] < bkm[i+1]){			min = bkm[i];			found_min = true;		}		if(found_min){			sum += max - min;		}	}	//右端点 	sum += bkm[n-1] <= bkm[n-2] ? bkm[n-2] : bkm[n-1];		return sum;}int main(){	int bkm[Big] = {};//所有神奇宝贝的战斗力 	int n = 0;//神奇宝贝的数量 	//输入 	cin>>n;	for(int i = 0; i < n; i++){		cin>>bkm[i];	}		int sum = amy(bkm, n);	cout<<sum;		return 0;}

2）初有问题版本

1-找到问题的输入测试

输入
5
5 1 4 1 7
运行结果

2-问题原因

代码中同时进行神奇宝贝的输入和处理，在找极大值和找极小值过程的衔接有问题。

后面改来改去，老出现新的bug，就干脆重写了。

3-版本代码

#include<iostream>
using namespace std;
int main(){
	int n=0;
	int temp=0;
	int sum=0;//军队的总战斗力 
	
	int i=0;
	int a=0;
	int b=0;
	
	cin>>n;
	
	while(true){		
		cin>>a;
		i++;
		//找局部最大值
		while(i<n){
			cin>>b;
			i++;
			if(a<b) a = b;
			else break;
		}
		int max = a;
		
		if(i == n){
			sum += max;
			break;
		}
		//找局部最小值
		while(i<n){
			cin>>b;
			i++;
			if(a>b) a = b;
			else break;
		}
		int min = a;
		
		if(i == n){
			sum += min;
			break;
		}
		//作差，加入总战斗力 
		sum += max - min;
	}
	
	cout<<sum;
	return 0;
} 

4.运行结果

5.算法分析

时间复杂度为：

o

(

n

)

o(n)

o(n)。

第二题：到迷宫出口的最短路径

1.题目

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。
输入描述
第一行是两个整数n和m(1<=n,m<=100)，表示迷宫的行数和列数。接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符’.‘表示空地，’#’表示墙，’S’表示起点,’T’表示出口。只能进行上、下、左、右四个方向的搜索。输出从起点到出口最少需要走的步数。
样式输入
3 3
S#T
.#.
…
样式输出
6

2.问题分析与算法设计思路

采用回溯法的思路，不过为了提高算法的效率，可以在搜索的过程中记录走过的地方。使用深度优先和广度优先都是可以的，我这里使用的深度优先搜索。

3.算法实现

代码：

//迷宫起点到出口的最短路径 
#include<iostream>
using namespace std;

int count=123456789;//到出口所用步数 

void dfs(char mg[100][100], int n, int m, int xy[2], int BuShu){
//	cout<<"xy:"<<xy[0]<<' '<<xy[1]<<endl;
	//出来了吗？
	if(mg[xy[0]][xy[1]] == 'T'){
		if(BuShu < count){
			count = BuShu;
		}
		return;
	} 
	//1
	if(xy[0] < n - 1) {
		mg[xy[0]][xy[1]] = '#';
		xy[0]++;
		if(mg[xy[0]][xy[1]] != '#'){
//			cout<<"下"<<endl;
			dfs(mg,n,m,xy,BuShu+1);
		}
		xy[0]--;
		mg[xy[0]][xy[1]] = '.';
	}
	//2
	if(xy[0] > 0) {
		mg[xy[0]][xy[1]] = '#';
		xy[0]--;
		if(mg[xy[0]][xy[1]] != '#'){
//			cout<<"上"<<endl;
			dfs(mg,n,m,xy,BuShu+1);
		}
		xy[0]++;
		mg[xy[0]][xy[1]] = '.';
	}
	//3
	if(xy[1] < m - 1) {
		mg[xy[0]][xy[1]] = '#';
		xy[1]++;
		if(mg[xy[0]][xy[1]] != '#'){
//			cout<<"右"<<endl;
			dfs(mg,n,m,xy,BuShu+1);
		}
		xy[1]--;
		mg[xy[0]][xy[1]] = '.';
	}
	//4
	if(xy[1] > 0) {
		mg[xy[0]][xy[1]] = '#';
		xy[1]--;
		if(mg[xy[0]][xy[1]] != '#'){
//			cout<<"左"<<endl;
			dfs(mg,n,m,xy,BuShu+1);
		}
		xy[1]++;
		mg[xy[0]][xy[1]] = '.';
	}
}

int main(){
	char mg[100][100] = {};
	int n=0;//迷宫的高(第一维） 
	int m=0;//迷宫的宽（第二维）
	int start[2]={};//起点位置 
	
	cin>>n>>m;
	
	//输入迷宫 
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin>>mg[i][j];
			if(mg[i][j] == 'S'){
				start[0] = i;
				start[1] = j;
			}
		}
	} 
	
	//走迷宫——深度搜索
	dfs(mg,n,m,start,0);
	
//	cout<<"count:"<<count<<endl;
	cout<<count<<endl;
	 
	return 0;
}

4.运行结果

5.算法分析

略😅

感谢阅读

博主主页：清风莫追

CSDN话题挑战赛第2期
参赛话题：学习笔记