蓝桥杯2019年第十届省赛真题-扫地机器人

题目

题目链接

题解

二分+贪心。

二分模板

看到这道题第一时间想到的就是二分和动规。仔细一看二分有戏，能check出来，所以决定用二分好好想想。（主要是因为我动规太菜了，怕了）

二分时间，准确的说我们二分的不是时间，而是覆盖范围，也就是枚举每个小机器人扫多少个方块；初始化l=1，一个小机器人最少扫一个，r=n，如果只有一个小机器人，那么它要扫全部。

重点是check函数。如何判断每个小机器人扫m块地是否可行呢？

一开始我的**（错误）思路**是以m为步长枚举每一段长度为m的区间，看看是不是存在小机器人在这段区间内，如果存在某个区间不存在小机器人，说明这个m取小了，返回false；如果每一段都有小机器人，说明每一段都可以被小机器人打扫到，所以返回true。

但是存在反例：

正确答案应该是m=4；但是按照上面的思路进行check，m=4时：

最后一段区间是没有小机器人打扫的，所以会判断返回false，即不可行。

我发现从10向1开始按照上面的思路枚举对于该样例好像可行哎，但是如果真的是正序枚举一遍再倒序枚举一遍这也太扯淡了，所以我就又开始思考别的思路。

贪心，我们贪心地去覆盖。我们将小机器人按照位置关系从小到大排序，枚举每个小机器人，每次枚举完一个小机器人都更新前面遍历过的这些小机器人能从头清扫到哪个小方格，这样一来，当我们枚举到当前小机器人时，我们先进行判断，看看当前小机器人向左边打扫，最远能打扫到哪里，如果没法与记录的前面的小机器人清扫的最右端的位置相拼接，那么说明我们二分到的这个m不可行，因为存在区域没被打扫啊，情况如下：

如果能够拼接，则我们要进行选择，可以选择拼接到前面的小机器人清扫的最右端的位置后面，也可以选择以小机器人作为覆盖的左端点，覆盖区间使劲向右延伸。当然，这两种选择不是在任意情况下都可取的，比如，当前面全部小机器人覆盖的右端点比当前小机器人还靠右，那么我们肯定不能把当前小机器人的清扫区间拼接到右端点后面吧，因为这段区间我们覆盖的太靠右了，以至于连当前小机器人都没覆盖上，所以我们要选择更左侧一点的区间覆盖，那就只能选择后者了，即以小机器人作为覆盖的左端点。为了代码更加简洁，我进行取min操作，这样就不用进行if判断了。

最后稍微注意一下，我们二分得到的小机器人最小最大覆盖个数，而真正让求的是打扫时间，也就是2*(ans-1)

虽然不是特别难，但自己AC出来真爽啊！

代码

#include
using namespace std;
const int N = 100100;

int n, k, a[N];

bool check (int m) {
// 注释部分为最初的错误思路，只能过36%
//	int l = 1, i = 0;
//	while (i < k) {
//		if (l  n) return true;
//	else return false;
	
	
	int r = 0; // r记录前面遍历的小机器人打扫到的右端点（含）
	for (int i = 0;i > n >> k;
	for (int i = 0;i > a[i];
	
	sort (a, a+k); // !
	
	int l = 1, r = n, m;
	while (l > 1;
		if (check (m)) r = m;
		else l = m + 1;
	}
	
	cout