萌新赛第（一）场
K以撒和隐藏房间
以撒又一次的逃进了地下室，地下室可以看作一个n*m的矩阵的迷宫，其中有些格子是有门相连房间，有些则是无法通过的墙壁。以撒发现其中一些墙壁似乎是空心的，可以通过爆炸打开隐藏的房间，而隐藏房的生成有一定的规律，以撒认为一个墙壁格子在满足以下所有情况时可能会是隐藏房间：
1， 该墙壁格子和三个普通房间相邻
2， 在满足1条件的情况下，不能和boss房间相邻
但是以撒正在和萌死戳交战，
现在你需要编写程序告诉他是否存在可能是隐藏房间的格子。
如果存在，输出两行，第一行是一个YES，第二行输出可能为隐藏房间的格子的数量
如果不存在，输出NO
输入描述:
第一行两个整数n，m(3<m,n<=1000)
然后是一个n*m矩阵，表示地图状态，0表示墙壁，1表示房间，2表示boss房间
输出描述:
如果存在，输出两行，第一行是一个YES，第二行输出可能为隐藏房间的格子的数量
如果不存在，输出NO
示例1
输入
3 3 001 110 211 输出 YES 1
示例2
输入
3 4
0010
1111
0102
输出
NO
备注:隐藏房间不属于房间题目分析
本题要找的是隐藏房间的格子的数量，题目说明一个墙壁格子在满足以下所有情况时可能会是隐藏房间，因此只要判断矩阵中的墙壁即字符‘0’是否满足题目条件即可，而且观察本题示例的输入，明显一行中的数与数之间没有空格，因此我们必须要把矩阵map数组定义为字符型，才能直接输入map[i][j],不能定义为整型，进行直接输入。本题我是输入m,n之后定义的数组map[n][m]，这样就需要检查数组是否越界，但如果是直接定义的map[1005][1005]，就无需检查边界，仅依赖于数组的额外空间即可。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;char map[n][m]; //字符数组for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>map[i][j];}}int cnt=0; //记录隐藏房间的格子的数量int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};for(int i=0;i<n;i++){for(int j=0;j<m;j++){int ans=0; //记录与该墙壁格子相邻的格子中普通房间个数bool mark=1;//标记是否与boss房间相邻，相邻为0if(map[i][j]!='0')continue;for(int k=0;k<4;k++){int ni=i+dx[k];int nj=j+dy[k];if(ni>=n||ni<0||nj>=m||nj<0)continue;if(map[ni][nj]=='1')ans++;if(map[ni][nj]=='2'){mark=0;break;}}if(ans==3&&mark)cnt++;}}if(cnt==0)cout<<"NO"<<endl;else{cout<<"YES"<<endl;cout<<cnt<<endl;}return 0;
}F松鼠排序
松鼠宝宝有一排n个大小不一的坚果，松鼠宝宝想把坚果从小到大排序，每次他会选择两个坚果a和b每次花费1点力气把这两个坚果交换，爱动脑筋的松鼠宝宝想知道他排完这n个坚果一共需要花费的最少力气是多少？
输入描述:
第一行一个整数n代表坚果数
接下来一行n个整数代表每个坚果的大小(每个坚果大小都不一样，即大小为1-n的一个排列)
1<=n<=1e5
坚果大小x，1<=x<=n
输出描述:
一行输出代表松鼠宝宝花费的最小力气
示例1
输入
3 3 2 1
输出
1
题目分析
本题目标是找到最少的交换次数，可使用贪心策略来最小化交换次数，具体是通过b[x]可以快速找到值为 x 的元素当前在数组中的位置，遍历每个位置 i，检查该位置的元素是否等于 i，如果不等于，说明需要交换。此时直接将值 i 放到位置 i 上，并将原来位置 i 的元素放到它应该在的位置，通过这种方式，每次交换至少能让一个元素归位，从而最小化交换次数，交换过程如下：
- 当发现
a[i] != i时，记录当前值 r = a [i] - 将 i 放到位置 i 上（a [i] = i）
- 更新值 r 的新位置为原来 i 的位置（b [r] = b [i]）
- 将原来位置 i 的元素放到值 r 原本所在的位置（a [b [i]] = r）
代码
#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int a[n+1],b[n+1];for(int i=1;i<=n;i++){cin>>a[i];b[a[i]]=i;}int sum=0;for(int i=1;i<=n;i++){if(a[i]!=i){sum++;int r=a[i];a[i]=i;b[r]=b[i];a[b[i]]=r;}}cout<<sum;return 0;
}