第一题：神奇宝贝大军
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 ] > a [ i − 1 ] 且 a [ i ] > a [ i + 1 ] a[i]>a[i-1]且a[i]>a[i+1]a[i]>a[i−1]且a[i]>a[i+1]
极小值：对于a [ i ] a[i]a[i]，需满足a [ i ] < a [ i − 1 ] 且 a [ i ] < a [ i + 1 ] a[i]<a[i-1]且a[i]<a[i+1]a[i]<a[i−1]且a[i]<a[i+1]
这样判断极值点更加清晰明确
对于端点单独考虑：
左端点：若a [ i ] > a [ i + 1 ] a[i]>a[i+1]a[i]>a[i+1]，则作为极大值。永远不作为极小值。
右端点：若a [ i ] > a [ i − 1 ] a[i]>a[i-1]a[i]>a[i−1]，则作为极大值；若a [ i ] < a [ i − 1 ] a[i]<a[i-1]a[i]<a[i−1]，则作为极小值；
程序过程：
输入神奇宝贝数组
遍历数组，对每个点进行分类（非极值点、极大值点、极小值点）
遍历过程中，每找到一个极小值（在这之前一定也找到了一个极大值），更新一次军队总战斗力：
总战斗力 + = 极大值 − 极小值 总战斗力+=极大值-极小值总战斗力+=极大值−极小值
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; } } //右端点 if(bkm[n-1] < bkm[n-2]){ min = bkm[n-1]; sum += max - min; } 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.运行结果
