蓝桥杯c++算法学习【2】之搜索与查找（九宫格、穿越雷区、迷宫与陷阱、扫地机器人：：：非常典型的必刷例题！！！）

别忘了请点个赞+收藏+关注支持一下博主喵！！！

关注博主，更多蓝桥杯nice题目静待更新:)

搜索与查找

一、九宫格

【问题描述】

        小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三 阶幻方指的是将1∼9不重复地填入一个3×3的矩阵当中，使得每一行、每一列和每 一条对角线的和都是相同的。

        三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八 为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美地构造出 一个九宫格来。

        

        有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操 作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉， 交给邻居家的小朋友进行还原，并且希望她能够判断出究竟是不是只有一个解。

        而你呢，也被小明交付了同样的任务，但不同的是，你需要写一个程序。

【输入格式】

        输入仅包含单组测试数据。 每组测试数据为一个3×3的矩阵，其中为0的部分表示被小明抹去的部分。 给出的矩阵至少能还原出一组可行的三阶幻方。

【输出格式】

        如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出 “TooMany”（不包含引号）

【样例输入】

        

【样例输出】 

        

解析：

举例说明：：： 

提示如下：

从n个不同元素中任取m（m⩽n）个元素，按照一定的顺序排列起来，叫作从n个 不同元素中取出m个元素的一个排列。

当m=n时所有的排列情况叫全排列，比如1,2,3的全排列有(1,2,3)、(1,3,2)、(2,1,3)、 (2, 3,1)、(3,1,2)、(3,2,1)。 

        对于n个数(1,2,3,...,n)，全排列的规模为 n！。本题 n 的大小固定为 9，9! = 362880， 规模较小，所以利用全排列是没有问题的，方法如下。

        （1）通过next_permutation 生成 1 ∼ 9 的全排列：(1,2,3,4,5,6,7,8,9)、(1,2,3,4,5,6, 7, 9,8)... 共 9! 种。

        （2）将所有生成的排列的第1∼3个数作为矩阵的第一行，第4∼6个数作为矩阵的 第二行，第7∼9个数作为矩阵的第三行（转换为全排列矩阵），如下图所示。

        （3）判断排列矩阵的每个部分是否和样例给定的矩阵相匹配（只看非零部分），如下图 所示。若匹配，则说明样例给定的矩阵可以还原为该排列矩阵。 

        （4）对于匹配的排列矩阵，判断其是否为一个九宫幻方（每一行、每一列和每一条对角线的和相同）。若为九宫幻方，则将其记录，并判断当前的九宫幻方的个数是否大于1，具体代码如下：

#include <bits/stdc++.h>
using namespace std;int p[10], a[5][5], b[5][5], ans[5][5];signed main() {for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)cin >> a[i][j]; // 读入样本矩阵for (int i = 1; i <= 9; i++)p[i] = i;int cnt = 0; // 统计九宫幻方的个数do {// 将排列转换为矩阵b[1][1] = p[1], b[1][2] = p[2], b[1][3] = p[3];b[2][1] = p[4], b[2][2] = p[5], b[2][3] = p[6];b[3][1] = p[7], b[3][2] = p[8], b[3][3] = p[9];// 判断排列矩阵和样本矩阵是否匹配bool flag = true; // flag = true 表示匹配，flag = false 表示不匹配for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {if (!a[i][j]) continue; // 只看非零部分if (a[i][j] != b[i][j])flag = false;}}if (!flag) continue; // 如果不匹配，就跳过// 判断排列矩阵是否是九宫幻方bool ok = true; // ok = true 表示排列矩阵是九宫幻方，ok = false 表示排列不是九宫幻方int sum = b[1][1] + b[2][2] + b[3][3]; // 取一条对角线的值if (sum != b[1][3] + b[2][2] + b[3][1]) continue; // 判断另一条对角线的和是否等于 sum，不等于就跳过for (int i = 1; i <= 3; i++) {int tmp1 = 0, tmp2 = 0; // tmp1 表示行的和，tmp2 表示列的和for (int j = 1; j <= 3; j++)tmp1 += b[i][j], tmp2 += b[j][i];if (tmp1 != sum || tmp2 != sum)ok = false; // 如果行的和或列的和不等于 sum，则排列矩阵不是九宫幻方}if (!ok) continue; // 如果不是九宫幻方，就跳过cnt++; // 九宫幻方的个数 + 1if (cnt >= 2) return cout << "Too Many\n", 0; // 九宫幻方的个数 >= 2，直接输出 Too Many，结束程序for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)ans[i][j] = b[i][j]; // 用 ans 记录下该九宫幻方} while (next_permutation(p + 1, p + 1 + 9));// 程序没有结束则说明 cnt <= 1。按照题意九宫幻方至少有一个，所以直接输出 ans 记录的矩阵即可for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)cout << ans[i][j] << "\n"[j == 3];return 0;
}

         本题也可使用DFS来处理。

        通过题意能分析出题目给我们布置的任务有下面几项。

        （1）将矩阵中为0的部分逐一修改为不重复的非零整数。

        （2）判断修改完后的矩阵是否是九宫幻方。

        （3）统计九宫幻方的个数。

        对于这些任务，我们可以分为4个步骤来完成。

        （1）将矩阵中为0的位置存储下来。

        （2）将矩阵中已出现过的数打上标记。

        （3）对于每个被存储下来的位置，尝试将其值修改为未被打上标记（未出现过）的数。

        （4）待所有被存储下来的位置都被修改后，判断矩阵是否为九宫幻方。若为九宫幻方， 则将其记录，并判断当前已出现的九宫幻方的个数是否大于1。

#include <bits/stdc++.h>
using namespace std;int vis[10], a[5][5], ans[5][5];
int n, cnt;
pair<int, int> p[10];bool check() {int sum = a[1][1] + a[2][2] + a[3][3]; // 取一条对角线的值if (sum != a[1][3] + a[2][2] + a[3][1]) return false; // 判断另一条对角线的和是否等于 sum，不等于则不是九宫幻方for (int i = 1; i <= 3; i++) {int tmp1 = 0, tmp2 = 0; // tmp1 表示行的和，tmp2 表示列的和for (int j = 1; j <= 3; j++)tmp1 += a[i][j], tmp2 += a[j][i];if (tmp1 != sum || tmp2 != sum) return false; // 如果行的和或列的和不等于 sum，则排列矩阵不是九宫幻方}return true; // 是九宫幻方
}void dfs(int now) {// now > n 表示所有被存储的位置都已经被修改if (now > n) {if (check()) { // 判断修改后的矩阵是否是九宫幻方cnt++; // 九宫幻方的个数 + 1// 用 ans 记录下该九宫幻方for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)ans[i][j] = a[i][j];}return;}int x = p[now].first, y = p[now].second;for (int k = 1; k <= 9; k++) {if (vis[k]) continue; // 如果 k 这个数已经存在，就不能被重复使用a[x][y] = k; // 尝试将该位置的值设置为 kvis[k] = 1; // k 被使用，为其打上标记dfs(now + 1); // 继续搜索// 回溯a[x][y] = 0;vis[k] = 0;}
}signed main() {for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++) {cin >> a[i][j]; // 读入样例矩阵if (!a[i][j]) p[++n] = make_pair(i, j); // 如果值为 0，就用 pair 存储下来vis[a[i][j]] = 1; // 将矩阵中已出现过的数打上标记}dfs(1); // 开始搜索if (cnt == 1) { // 九宫幻方的个数为 1，直接输出 ans 记录的矩阵for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)cout << ans[i][j] << "\n"[j == 3];} elsecout << "TooMany\n"; // 九宫幻方的个数为 2，则输出 TooManyreturn 0;
}

二、穿越雷区

【问题描述】

        X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。 

        某坦克需要从A区到B区去（A,B区本身是安全区，没有正能量或负能量特征）， 怎样走才能路径最短?

        已知的地图是一个方阵，上面用字母标出了A,B区，其他区都标了正号或负号分别 表示正、负能量辐射区。

         例如：

        

        坦克车只能水平或垂直方向上移动到相邻的区。

【输入格式】

         第一行是一个整数n，表示方阵的大小，4 ⩽ n < 100。

        接下来是n行，每行有n个数据，可能是 A，B，+，− 中的某一个，中间用空格分开。 A，B都只出现一次。

【输出格式】

        输出一个整数，表示坦克从A区到B区的最少移动步数。 如果没有方案，则输出−1。

【样例输入】

        

【样例输出】

         10

解析：

举例说明： 

        对于方阵上的某个位置，我们将其视作一个点，并用二维坐标来表示：(x,y)表示第x行 第y 列。

        对于点的正负能量值，可以使用二维数组a来表示。a[x][y]=1表示点(x,y) 的能量值 为正，a[x][y] = 0 表示点 (x,y) 的能量值为负，a[x][y]=−1 表示点 (x,y) 没有能量特征（A 点、B 点）。

        由于每次移动只能移动到相邻的位置，所以如果从(x,y)出发，只可能移动到(x+1,y) 或(x−1,y) 或 (x,y+1) 或 (x,y−1)。需要注意以下两点。

        （1）在移动的过程中，不能离开方阵（1⩽x,y⩽n）。

        （2）已经走过的位置，不重复走。 

（提示：因为第一次到达某个点和第二次到达某个点唯一的区别只在于它们的移动步数不同。根 据BFS的性质，第一次到达该点的移动步数一定小于等于第二次到达该点的移动步数， 所以为了保证移动步数最小，一个点只能经过一次。）

        （3）正负能量交替走。这是题目给定的限制条件。

        那么在移动的过程中，我们需要维护哪些信息呢?

        首先肯定要记录移动时的坐标信息，以此来判断是否到达了B点（也可用来判断当前位置的正负能量值）；其次需要记录移动的步数，这样到达B点后才能知道走了多少步。

        分析了移动时需要记录的信息后，就可以制定一个解题步骤。

        （1）读入并记录方阵的正负信息，记录A点和B点的坐标信息。

        （2）从A点开始BFS：

                •要求移动的正确性（不离开方阵、正负交替走）；

                •记录移动中的点的坐标、移动的步数、正负信息；

                •到达B点停止搜索，返回到达B点的移动步数。        

 

#include <bits/stdc++.h>
using namespace std;const int N = 1e2 + 10;
int nex[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 表示移动时的4个方向
int n, a[N][N]; // a[i][j]表示点的正负信息。a[i][j]=1表示点(i,j)的能量值为正，a[i][j]=0表示点(i,j)的能量值为负，a[i][j]=-1表示点(i,j)为B
int vis[N][N]; // vis[i][j]表示在搜索的过程中点是否走过。vis[i][j]=1表示点(i,j)已经走过，vis[i][j]=0表示点(i,j)还没走过
pair<int, int> st, ed; // st记录点A的位置，ed存储点B的位置struct node {int x, y, cnt;
};bool check(int x, int y) {if (x < 1 || x > n || y < 1 || y > n || vis[x][y]) return false;return true;
}int bfs(int x, int y) {pair<int, int> u = make_pair(x, y);queue<node> que;que.push(node{x, y, 0});vis[x][y] = 1;while (!que.empty()) {node u = que.front();if (u.x == ed.first && u.y == ed.second) return u.cnt;que.pop();int x = u.x, y = u.y;for (int i = 0; i <= 3; i++) {// (tx, ty)为(x-1, y)或(x+1, y)或(x, y-1)或(x, y+1)int tx = x + nex[i][0];int ty = y + nex[i][1];// a[tx][ty]的能量特征不能等于a[x][y]的能量特征if (!check(tx, ty) || a[tx][ty] == a[x][y]) continue;vis[tx][ty] = 1;que.push(node{tx, ty, u.cnt + 1});}}return -1;
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {char x;cin >> x;if (x == 'A') {st.first = i;st.second = j;a[i][j] = -1;} else if (x == 'B') {ed.first = i;ed.second = j;a[i][j] = -1;} else if (x == '+') {a[i][j] = 1;} else {a[i][j] = 0;}}}cout << bfs(st.first, st.second) << '\n';return 0;
}

        这道题也可以用DFS来做，总体思路不变。

        （1）读入并记录方阵的正负信息，记录A点、B点的坐标。

        （2）从A点开始DFS：

                 •要求移动的正确性（不离开方阵、正负交替走）。

                •记录移动中的点的坐标、移动的步数、正负信息。

                 •到达B点停止搜索，返回到达B点的移动步数。 

#include <bits/stdc++.h>
using namespace std;const int N = 1e2 + 10;
int n, ans; // ans 记录答案
int a[N][N]; // a[i][j] 表示点的正负信息。a[i][j] = 1 表示点 (i, j) 的能量值为正，a[i][j] = 0 表示点 (i, j) 的能量值为负，a[i][j] = -1 表示点 (i, j) 为 B
int vis[N][N]; // vis 记录到达 (x, y) 的移动步数
pair<int, int> st, ed; // st 记录点 A 的位置，ed 存储点 B 的位置void dfs(int x, int y, int cnt) {// x, y 表示当前点的位置，cnt 表示到达该点的移动步数if (cnt > ans) return; // 剪枝：如果移动步数大于 ans，那么该走法一定不是最优的，就没必要走下去了if (cnt > vis[x][y]) return; // 剪枝：如果到达 (x, y) 的移动步数大于 vis[x][y]，说明从起点走到 (x, y) 有更优的走法，那么该走法到达终点的移动步数一定不是最优的if (x < 1 || x > n || y < 1 || y > n) return; // 保证移动的正确性if (x == ed.first && y == ed.second) {ans = cnt; // 到达终点，记录（更新）答案return;}// 记录（更新）走到 (x, y) 的移动步数vis[x][y] = cnt;// a[tx][ty] 的能量特征不能等于 a[x][y] 的能量特征int tx, ty;tx = x - 1, ty = y;if (a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);tx = x + 1, ty = y;if (a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);tx = x, ty = y - 1;if (a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);tx = x, ty = y + 1;if (a[tx][ty] != a[x][y]) dfs(tx, ty, cnt + 1);
}signed main() {cin >> n;ans = 0x3f3f3f3f;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)vis[i][j] = 0x3f3f3f3f;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {char x;cin >> x;if (x == 'A') {st.first = i;st.second = j;a[i][j] = -1;} else if (x == 'B') {ed.first = i;ed.second = j;a[i][j] = -1;} else if (x == '+') {a[i][j] = 1;} else {a[i][j] = 0;}}}dfs(st.first, st.second, 0);cout << ans << '\n';return 0;
}

三、迷宫与陷阱

【问题描述】

        小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由N×N个格子组成的2D迷宫。

        小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

        每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

        迷宫中有些格子小明可以经过，我们用'.'表示。

        有些格子是墙壁，小明不能经过，我们用'#'表示。

        此外，有些格子上有陷阱，我们用'X'表示。

        除非小明处于无敌状态，否则不能经过。

        有些格子上有无敌道具，我们用'%'表示。

        当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续K步。

        之后如果再次到达该格子不会获得无敌状态了。

        处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

         给定迷宫，请你计算小明最少经过几步可以离开迷宫?

【输入格式】

         第一行包含两个整数N,K(1⩽N⩽1000,1⩽K⩽10)。 以下N行包含一个N×N的矩阵。 矩阵保证左上角和右下角是'.'。

【输出格式】

        一个整数表示答案。如果小明不能离开迷宫，输出−1。

【样例输入】

        

【样例输出】

         10

解析：

举例说明： 

        这是一道BFS解迷宫的“变种题”。对于迷宫的格子，我们习惯性用二维坐标来表示，如 (x, y) 表示位于第 x 行第y 列的格子。

         在开始解题前，我们先来分析一下迷宫上格子的类型，如下图所示 ：

        （1）.：普通的格子，小明可以经过。

        （2）#：墙壁，小明不能经过。

        （3）%：拥有无敌道具的格子，小明经过该格子后会进入无敌状态并持续K步，但格子 会变为普通的格子。

        （4）X：陷阱，如果处在无敌状态则可以经过，否则不可以经过。 、

        分析了迷宫的结构后，我们来思考移动时需要记录的信息：

        （1）需要记录移动的坐标，这样才能判断是否到达终点；

        （2）需要记录移动的步数，这样才能知道到达终点后走了多少步；

        （3）需要记录移动到下一个位置时的状态（无敌状态或普通状态），这样才能判断能否 经过陷阱。

        我们可以定义结构体来表示它们，代码如下。 

struct node {int x, y;      // 表示移动到的位置int cnt;       // 表示移动的步数int status;    // 表示接下来的 status 步都将保持无敌状态。status > 0 则处于无敌状态，status = 0 则处于普通状态
};

        那么对于这些信息，如果从一个位置(x,y)移动到下一个位置，会发生哪些变化呢?

        （1）坐标会变为(x+1,y) 或 (x−1,y) 或 (x,y+1) 或 (x,y−1)。

        （2）移动的步数会+1。

        （3）移动到下一个位置时的状态：

         • 如果是普通状态，则有可能保持普通状态，也可能变为无敌状态；

         • 如果是无敌状态，则有可能保持无敌状态，也可能变为普通状态。

         具体的状态变化分以下几种情况。

         1. 普通状态

        （1）如果下一个位置是拥有无敌道具的格子，则状态变为无敌状态，且接下来的K步都 将保持无敌状态。

        （2）如果下一个位置是普通的格子，则状态不变。

        2. 无敌状态

        （1）如果下一个位置是拥有无敌道具的格子，则状态保持无敌状态，且接下来的K步都 将保持无敌状态。

         （2）如果下一个位置是普通的格子或陷阱，就要判断距离上一次成为无敌状态已经走了多少步。

        • 如果已经走了K步，则状态变为普通状态。

        • 如果还没走K步，则状态保持普通状态。 

        确定了移动时需要记录的信息、移动时信息的变化，我们再来思考一个问题，即已经走 过的点还可以继续走吗?

        答案肯定是可以（只要移动是合法的就可以走）。但是，有没有再走一次的必要呢?

        判断有没有必要即判断第二次走到该点时的信息是否优于第一次走到这个点时的信息， 如果优于则有必要，反之没有必要。

        那么怎么判断移动信息的优劣呢? 显然，移动的步数越少越好，可保持无敌的状态越久 越好。

        假设上一次走到(x,y) 时，有以下两种情况。

        （1）移动的步数为cnt1。

        （2）接下来的status1 步都将保持无敌状态。

         此次走到(x,y) 时有以下两种情况。

        （1）移动的步数为cnt2。

         （2）接下来的status2 步都将保持无敌状态。

        那么会有以下几种情况。

        （1）cnt1 < cnt2，status1 > status2：由于此次移动的步数、可保持无敌状态的步数都 劣于上一次，所以完全没必要再走一次。

        （2）cnt1 > cnt2，stauts1 < status2：由于此次移动的步数、可保持无敌状态的步数都 优于上一次，所以是有必要再走一次的。

         （3）cnt1 > cnt2，stauts1 < stauts1：此次移动的步数优于上一次，但可保持无敌状态 的步数劣于上一次，无法判断哪种情况更优。为了保险起见，还是有必要再走一次的。

        （4）cnt1 < cnt2，status1 > status2：此次移动的步数劣于上一次，但可保持无敌状态 的步数优于上一次，无法判断哪种情况更优。为了保险起见，还是有必要再走一次的。

         根据BFS 的性质，一定满足第一次走到(x,y)的移动步数<第二次走到(x,y)的移动 步数<第三次走到(x,y)的移动步数<……

        因此，我们只要对status 作出判断就好，如下图所示。 

        完成上面的分析与思考后，就可以设计具体的解题步骤了。

        （1）读入迷宫，并用a[][] 来存储各个格子的类型。

        • 普通的格子用0表示（a[x][y]=0）。

        • 拥有无敌道具的格子用1表示（a[x][y]=1）。 • 陷阱用2表示（a[x][y]=2）。

         • 墙壁用3表示（a[x][y]=3）。

        （2）从点(1,1) 开始 BFS，要求如下。

         • 要求移动的正确性（不离开迷宫；不能经过墙壁；普通状态下不能经过陷阱）。

         • 保证移动的必要性（对于没走过的格子，有必要走一次；对于走过的格子，判断有没 有再走一次的必要）。 

        • 记录移动中的点的坐标、移动的步数、可保持无敌状态的步数。

         • 到达(n,n) 点停止搜索，返回到达(n,n) 点的移动步数。 

#include <bits/stdc++.h>
using namespace std;const int N = 1e3 + 10;struct node {int x, y;      // 表示移动到的位置int cnt;       // 表示移动的步数int status;    // 表示接下来的 status 步都将保持无敌状态。status > 0 则处于无敌状态，status = 0 则处于普通状态
};int n, k;
int nex[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 表示移动时的4个方向
int a[N][N], vis[N][N], s[N][N]; // a[][] 表示格子的类型，vis[][] 标记格子是否被访问过，s[][] 记录经过格子时最大的可保持无敌状态的步数bool check(int x, int y, int status) {// 不能离开迷宫，不能经过墙壁if (x < 1 || x > n || y < 1 || y > n || a[x][y] == 3) return false;// 如果不是无敌状态，不能经过陷阱if (a[x][y] == 2 && !status) return false;return true;
}int bfs() {queue<node> que;que.push(node{1, 1, 0, 0}); // 从 (1, 1) 出发vis[1][1] = 1; // 标记 (1, 1) 被访问过while (!que.empty()) {node u = que.front();que.pop();if (u.x == n && u.y == n) return u.cnt; // 到达 (n, n) 点则停止搜索for (int i = 0; i <= 3; i++) {int tx = u.x + nex[i][0];int ty = u.y + nex[i][1];if (!check(tx, ty, u.status)) continue;int status = max(0, u.status - 1);if (a[tx][ty] == 1) { // 陷阱vis[tx][ty] = 1;a[tx][ty] = 0; // 陷阱走过就变为普通的格子que.push(node{tx, ty, u.cnt + 1, k});} else { // 普通的格子if (!vis[tx][ty]) { // 如果没有走过，那么有必要走一次vis[tx][ty] = 1;que.push(node{tx, ty, u.cnt + 1, status});continue;}if (status <= s[tx][ty]) continue; // 可保持的无敌状态劣于上一次，没有必要再走一次// 可保持的无敌状态优于上一次，有必要再走一次s[tx][ty] = status;que.push(node{tx, ty, u.cnt + 1, max(0, status)});}}}return -1;
}signed main() {cin >> n >> k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {char x;cin >> x;if (x == '%') a[i][j] = 1;else if (x == 'X') a[i][j] = 2;else if (x == '#') a[i][j] = 3;}}cout << bfs() << '\n';return 0;
}

四、扫地机器人

【问题描述】

        小明公司的办公区有一条长长的走廊，由N个方格区域组成，如下图所示。

        

        走廊内部署了K台扫地机器人，其中第i台在第Ai个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干净。

        请你编写一个程序，计算每台机器人的清扫路线，使得

        （1）它们最终都返回出发方格。

        （2）每个方格区域都至少被清扫一遍。 

        （3）从机器人开始行动到最后一台机器人归位花费的时间最少。

         注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。

        输出最少花费的时间。在上图所示的例子中，最少花费时间是6。第一台路线：2-1 2-3-4-3-2，清扫了1,2,3,4号区域。第二台路线5-6-7-6-5，清扫了5,6,7。第三台路线 10-9-8-9-10，清扫了8,9和10。

【输入格式】

        第一行包含两个整数N,K。 接下来K行，每行一个整数Ai。 其中，1K<N10的5次方, 1AiN。

【输出格式】

        输出一个整数表示答案。

【样例输入】

        

【样例输出】

        6

解析:

举例说明： 

        本题的3个关键信息包括清扫的时间、清扫的方法、清扫的区域面积（方格个数）。

         其中清扫的（最短）时间是我们要求的答案，清扫的区域面积（方格个数）是已知的，而 清扫的方法由我们自己决定。

        显然，在同等时间下，使用效率高的清扫方法，清扫的区域面积（方格个数）就会多。反过来同理，要让所有区域都至少被清扫一遍，且清扫的时间最短，就需要用最有效率的清扫方法。

        那么问题来了，什么样的方法是最有效率的呢?

1. 求最优的清扫方法

        假设有k台机器人，它们从左到右的编号分别为1,2,...,k，每台机器人清扫的时间为t 分钟。

        按照顺序，我们会从1号机器人左边的区域（可能为空）开始处理。

        我们有1∼k台机器人，要选择哪台机器人去清扫这部分区域呢?

        显然，让1号机器人去清扫效率会是最高的。如果让其他机器人清扫，就需要多花费一 些时间（注意，此时只考虑第一台机器人左边的区域，而不考虑其他区域），如下图所示。

        1 号机器人清扫完它左边的区域后，需要返回原位。返回原位后，如果还剩有时间，我们不能浪费，要让它继续去清扫它右边的区域，如下页图所示。这样可以减少下一台机器人需要往左清扫的范围（即减少下一台机器人的清扫时间） 

 

        不难发现，在忽略了已清扫完毕的区域后，原来的灰色区域相当于现在的红色区域，原 来的第一台机器人相当于现在的第二台机器人，回到了和开始几乎一样的情况。

         因此，可根据贪心思想确定清扫方法，即让每台机器人都要优先清扫其左边还未扫过的 格子，然后再往右清扫，以保证每次清扫的效率都最高。

         确定了清扫的方法、清扫的区域面积，我们就可以求清扫的时间。

2. 求最少的清扫时间

        在开始求最少的清扫时间之前，我们需要明确以下两点。

        （1）如果所有机器人在时间 t 内都用了效率最高的清扫方法，却没能清扫完所有区域， 那么问题就只能出在“t太小（时间不够）”上。

        （2）如果所有机器人都用了效率最高的清扫方法，那么给的时间越多，可清扫的区域就会越多（在达到某个临界点之后，随着时间的增加，可清扫的区域个数将不会变化）。

       由上，我们可以得出对于一个时间t，它要想作为答案须满足以下两个条件。

        （1）所有的机器人在t分钟内可清扫所有区域。

        （2）t 是满足所有条件1的时间中最小的一个。 对于条件1，我们可以模拟清扫的方法，从1号机器人开始一个个清扫区域。在所有机 器人清扫结束后判断是否清扫了所有区域即可（见下页图），代码如下。

#include <bits/stdc++.h>
using namespace std;int main() {int n, k;cin >> n >> k;vector<int> a(k);for (int i = 0; i < k; ++i) {cin >> a[i];}int pos = 0; // pos 用来表示 1~pos 区域已被清扫，pos+1~n 区域未被清扫for (int i = 0; i < k; ++i) {if (pos < a[i]) {// 往左清扫，需要花费的时间为 2 * (a[i] - pos - 1)int time_spent = 2 * (a[i] - pos - 1);pos = a[i] - 1; // 更新 pos 为 a[i] - 1，因为 a[i] - 1 之前的区域已经清扫完毕// 如果还有剩余时间if (time_spent < 2 * (n - pos - 1)) {// 往右清扫，可清扫的区域的个数为剩余的时间 / 2int remaining_time = 2 * (n - pos - 1) - time_spent;pos += remaining_time / 2;}}}// 判断 pos 是否大于等于 nif (pos >= n) {cout << "清扫完成" << endl;} else {cout << "未清扫完成" << endl;}return 0;
}

        由于需要遍历所有机器人，所以复杂度为O(k)。

        对于条件2，我们可以由小到大去枚举t，这样第一个满足条件1的t就是答案。 

        不过需要注意的是，当题目给定的测试数据较为极端时，使用最优的清扫方法也可能需 要接近2×n的时间才可清扫完所有区域，即我们枚举的次数将接近2×n。那么要想同时满足条件1、条件2，需要的时间复杂度就为O(n×k)。

        这并不是最好的做法，我们来考虑一下如何优化复杂度。

        已知本题的目的是求在使用最高效方法的前提下，清扫完所有区域所需要花费的最少时 间。而根据上文分析可得：随着时间增加，可清理的区域只会多不会少。这说明时间是满足 单调性的。

        那么，我们就可以将用枚举法求t替换为用二分法求t来降低时间复杂度。

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int n, k, a[N]; // a[i] 表示第 i 台机器人的位置bool check(int mid) {int pos = 0; // pos 用来表示 1~pos 区域已被清扫，pos+1~n 区域未被清扫for (int i = 1; i <= k; i++) { // 遍历 k 台机器人int t = mid;if (pos < a[i]) {t -= (a[i] - pos - 1) * 2; // 往左清扫，需要花费的时间为 2 * (a[i] - pos - 1)}if (t < 0) return false; // 如果时间小于 0，说明无法清扫完左边的区域，时间不够pos = a[i] + t / 2; // 如果还剩有时间，继续向右清扫}if (pos < n) return false; // 如果没有清扫完所有的区域，则说明时间不够return true;
}signed main() {cin >> n >> k;for (int i = 1; i <= k; i++) cin >> a[i];sort(a + 1, a + 1 + k); // 位置排序int l = 0, r = 2 * n, ans = 2 * n;while (l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;r = mid - 1;} else {l = mid + 1;}}cout << ans << '\n';return 0;
}

别忘了请点个赞+收藏+关注支持一下博主喵！！！

关注博主，更多蓝桥杯nice题目静待更新:)