[蓝桥杯]扫地机器人

扫地机器人

题目描述

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

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

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

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,KN,K。

接下来 KK 行，每行一个整数 AiAi​。

其中，1≤K<N≤105，1≤Ai≤N1≤K<N≤105，1≤Ai​≤N。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

10 3
5
2
10

输出

6

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 3612  |  总提交次数: 4298  |  通过率: 84%

难度: 困难   标签: 2019, 省赛, 搜索, 二分

C++代码实现：扫地机器人路径规划

算法思路

本题需要解决多机器人协同覆盖所有区域并最小化最大耗时的问题。核心思路是​​二分答案+贪心验证​​：

1. ​​二分答案​​：确定最小化最大耗时的范围（0 ~ 2*(N-1)），通过二分查找找到满足覆盖条件的最小时间。
2. ​​贪心验证​​：
   • 每个机器人在时间T内可覆盖的最大区间长度为 len_max = T/2 + 1
   • 对机器人位置排序后，从左到右处理：
     • 若机器人位置 > 当前覆盖边界：检查能否覆盖空隙并扩展边界
     • 若机器人位置 ≤ 当前覆盖边界：利用机器人扩展右侧边界
   • 最终检查是否覆盖整个区间[1, N]

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int N, K;
vector<int> robots;bool check(int T) {int len_max = T / 2 + 1;  // 计算最大覆盖长度int cur = 0;               // 当前已覆盖的最右位置for (int i = 0; i < K; i++) {if (cur >= N) break;   // 提前终止：已完全覆盖if (robots[i] > cur) {if (robots[i] - cur > len_max) return false;  // 无法覆盖空隙cur = min(N, cur + len_max);  // 向右扩展边界} else {cur = min(N, robots[i] + len_max - 1);  // 从当前位置向右扩展}}return cur >= N;  // 检查完全覆盖
}int main() {cin >> N >> K;robots.resize(K);for (int i = 0; i < K; i++) cin >> robots[i];sort(robots.begin(), robots.end());  // 关键：按位置排序int left = 0, right = 2 * (N - 1);  // 二分边界while (left < right) {int mid = (left + right) / 2;if (check(mid)) right = mid;     // 满足则缩小上界else left = mid + 1;  // 不满足则增大下界}cout << left << endl;return 0;
}

代码解析

1. ​​输入处理​​：
   • 读取走廊长度 N 和机器人数量 K
   • 存储机器人初始位置并排序（确保从左到右处理）
2. ​​验证函数 check(T)​​：
   • len_max = T/2 + 1：计算机器人在时间T内可覆盖的最大连续区间长度
   • 贪心策略：维护当前覆盖边界 cur，根据机器人位置决定扩展方式
3. ​​二分框架​​：
   • 初始化边界 [0, 2*(N-1)]
   • 通过 check(mid) 判断时间可行性，收敛到最小时间

实例验证

​​输入样例​​：

10 3
5
2
10

​​执行过程​​：

1. 机器人排序后位置：[2, 5, 10]
2. 二分查找过程：
   • T=6时 len_max=4
   • 机器人2：覆盖[1,4] → cur=4
   • 机器人5：覆盖[5,8] → cur=8
   • 机器人10：覆盖[9,10] → cur=10
   • 满足条件，输出6

测试要点

1. ​​边界情况​​：
   • N=1, K=1：机器人无需移动（输出0）
   • N=2, K=1：机器人需覆盖[1,2]（输出2）
   • 机器人位置重复：确保覆盖逻辑正确
2. ​​性能测试​​：
   • N=100000, K=50000：验证二分效率（<1s）
3. ​​特殊分布​​：
   • 机器人集中在左侧/右侧
   • 机器人均匀分布

优化建议

1. ​​提前终止​​：在 check() 中一旦 cur≥N 立即退出循环
2. ​​二分优化​​：使用 mid = left + (right-left)/2 避免溢出
3. ​​输入加速​​：

   ios::sync_with_stdio(false);
   cin.tie(0);  // 加速输入输出

4. ​​并行计算​​：若K极大时，可将机器人分组并行验证（本题K<10⁵无需）

注意事项

1. ​​必须排序​​：未排序机器人位置会导致贪心策略失效
2. ​​整数除法​​：T/2 在C++中自动取整，与数学公式一致
3. ​​时间范围​​：上界 2*(N-1) 是最坏情况（单个机器人覆盖全部）
4. ​​重叠覆盖​​：允许机器人覆盖重叠区域，不影响正确性