LLX

用户名：884843819

访问量：3697

签　名：

这个人很懒什么都没有留下

等　　级
排　　名	1904
经　　验	2470
参赛次数	3
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2019年第十届真题-扫地机器人-题解（C++代码）
浏览：2934

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

蓝桥杯2019年第十届真题-扫地机器人-题解（C++代码）

　　作者: LLX　　　　发表时间：2020-03-28 14:45:15 浏览：2934　|　评论：1　

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

**解题思路**
模拟机器人扫地区域

首先设定一个机器人可活动的区间大小 Q ,
则 Q 的最小范围应是 N / K 或者 第一个机器人的下标
由于要模拟扫地区域 我们可以设定一个 左边界 L 使 L 左边的区域都已经被清扫过
遍历所有机器人 并根据当前区间的大小更新左边界
每个机器人先向左 寻找是否有未清扫的区域。
若 机器人向左 可以扫到的 最大区域 未到达边界处 说明当前区间不满足条件
如果满足条件 根据机器人清扫区间更新边界 L
当机器人出现在边界左边时 ( L : 边界 ， i : 当前机器人的下标 ， Q : 区间大小 )
L = i + Q -1
当机器人出现在边界右边时
L = i + Q - ( i - L)

ac代码
	#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int n , k;
    int a[100005]; 
    
    bool f(int l, int Q){ // l 左边界  Q 区间大小  
    	
    	 for(int i = 0; i < k; i++){
    	 	
    	 	if(a[i] - Q <= l){  // 若 当前机器人的下标 减去 区间大小 <= 左边界的时候 说明可以继续 否则退出 
    	 		if(a[i] <= l) l = a[i] + Q -1; // 若机器人 在左边界内 边界就该等于机器人向右所能扫到的最远点 
    			else l = a[i] + Q - (a[i] -  l );
    	 	} else return false;
    	 }
    	 if(l < n) return false; // 遍历完机器人 若左边界小于 n 则说明没有全部清扫 
    	 return true;
    }
    
    int main(){
    	cin >> n >>k;
    	for(int i = 0; i < k; i++)
    		scanf("%d",&a[i]);
    	sort(a,a+k);
    	
    	int Q; // 区间大小
    	Q = (n/k) >= a[0] ? n/k : a[0]; // 区间初始化 最小可能的区间
    	for(; Q <= n; Q++){
    		int l = 0; // 左边界  初始为 0 
    		if(f(l,Q)) break;
    	}
    	cout << 2*(Q-1); // 步数 = (区间大小 - 1) * 2 
    	return 0;
    }
PS: 代码其实有一个小问题 后来发现的
当 n = k 的时候 会走 2 步 加个判断 n = k 直接输出就行了
题目要求 k < n 所以就懒得改
用二分会更快

0.0分

25 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

水里的氯化氢

请问 步数 = (区间大小 - 1) * 2 是怎么得出来的呢

2021-03-11 15:03:22

LLX

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-等差数列（C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

printf基础练习2 （C语言代码）

蓝桥杯2019年第十届真题-扫地机器人-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

wu-淘淘的名单（C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

程序员的表白（C语言代码）

LLX

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-等差数列 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

printf基础练习2 （C语言代码）

蓝桥杯2019年第十届真题-扫地机器人-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

wu-淘淘的名单 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

程序员的表白 （C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

wu-淘淘的名单（C++代码）

程序员的表白（C语言代码）