爱网站关键词查询,wordpress 不显示文章图片,做网站需要电脑吗,广告发布计划怎么写文章目录 扫地机器人题目描述解题思路二分贪心 扫地机器人
题目描述
小明公司的办公区有一条长长的走廊#xff0c;由 N 个方格区域组成#xff0c;如下图所 示。 走廊内部署了 K 台扫地机器人#xff0c;其中第 i 台在第 Ai 个方格区域中。已知扫地机器人每分钟可以移动… 文章目录 扫地机器人题目描述解题思路二分贪心 扫地机器人
题目描述
小明公司的办公区有一条长长的走廊由 N 个方格区域组成如下图所 示。 走廊内部署了 K 台扫地机器人其中第 i 台在第 Ai 个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中并将该区域清扫干净
请你编写一个程序计算每台机器人的清扫路线使得 它们最终都返回出发方格 每个方格区域都至少被清扫一遍 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域它们不会互相影响
输出最少花费的时间。在上图所示的例子中最少花费时间是 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。
输出描述
输出一个整数表示答案
样例输入
10 3
5
2
10样例输出
6解题思路
首先这题需要找到最少花费时间那么我们先二分机器人的扫地范围最小为0最大为n一旦所有机器人能扫完全程说明该值是符合条件的然后二分缩小范围直到找出最小的值刚好所有机器人能够扫完全程。
check函数的实现
首先我们需要明确mid是机器人的扫地步数如果mid为1那么机器人就扫机器人当前的格子。然后开始贪心思路我们尽可能让机器人先扫完自己右边的然后有多余的步数再扫自己左边的。情况一如果a[i]-xs就说明机器人扫不完自己右边的格子直接返回false 情况二如果前一个机器人往右多扫了几格S应该更新为s a[i] x - 1 如果上述两种情况都不属于将s向前推进x个方格s x 最后如果S大于等于地图范围n返回true否则说明机器人没走完全程返回false
二分贪心
这段代码是一个用于解决扫地机器人问题的C程序。程序的目的是通过编写一个算法使得多台扫地机器人能够高效地清扫一个由N个方格区域组成的走廊并最终返回各自的出发点。下面是对代码的详细注释
#includebits/stdc.h // 引入C标准库的头文件bits/stdc.h是一个非标准的宏定义包含了常用的头文件
using namespace std; // 使用标准命名空间简化标准库中的类和函数的引用// 定义全局变量
int n, k; // n表示走廊的方格数k表示扫地机器人的数量
int a[100010]; // 数组a用于存储k台扫地机器人的初始位置// check函数用于判断在给定的清扫时间x下是否所有方格都被清扫过
bool check(int x) {int s 0; // s表示当前已清扫的方格区域的右边界for(int i 0; i k; i) { // 遍历所有的扫地机器人if(a[i] - x s) return false; // 如果机器人i需要清扫的区域超出了当前已清扫的范围则返回falseif(s a[i]) s a[i] x - 1; // 如果当前已清扫的范围已经包含了机器人i的位置则更新s为机器人i的清扫结束位置else s x; // 否则将s向前推进x个方格}return s n; // 如果s到达或超过了走廊的最后一个方格则说明所有方格都被清扫过返回true
}int main() {cin n k; // 从标准输入读取走廊的方格数和机器人的数量for(int i 0; i k; i) // 遍历并读取每台机器人的初始位置cin a[i];sort(a, a k); // 对机器人的初始位置进行排序这有助于后续的二分查找// 二分查找查找满足条件的最小时间xint l 0, r n; // 定义二分查找的左右边界初始时左边界为0右边界为走廊的方格数nwhile(l r) { // 当左边界小于右边界时继续查找int mid l r 1; // 计算中间值midif(check(mid)) r mid; // 如果在时间x下可以完成清扫则尝试查找更小的时间else l mid 1; // 否则需要增加时间}cout 2 * (r - 1) endl; // 输出最终结果即2倍的最小时间因为题目要求的是最少花费的时间的两倍return 0; // 程序结束
}这段代码使用了二分查找算法来找到满足条件的最小时间x。在每次迭代中它都会检查一个中间值是否满足条件然后根据结果调整查找范围。最终找到的最小时间x是满足所有方格至少被清扫一次且机器人能够返回出发点的最小时间。由于题目要求输出的是这个时间的两倍所以在输出时乘以2。
