洛阳住房与城乡建设厅网站,临沂市建设局官方网站,外贸网站有哪些平台,百度网站关键词优化在哪里做题目描述
小明公司的办公区有一条长长的走廊#xff0c;由 NN 个方格区域组成#xff0c;如下图所示。 走廊内部署了 KK 台扫地机器人#xff0c;其中第 ii 台在第 A_iAi 个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中#xff0c;并将该区域清扫干净。…题目描述
小明公司的办公区有一条长长的走廊由 NN 个方格区域组成如下图所示。 走廊内部署了 KK 台扫地机器人其中第 ii 台在第 A_iAi 个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中并将该区域清扫干净。
请你编写一个程序计算每台机器人的清扫路线使得 它们最终都返回出发方格 每个方格区域都至少被清扫一遍 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域它们不会互相影响。
输出最少花费的时间。 在上图所示的例子中最少花费时间是 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。 输出描述
输出一个整数表示答案。 我们不妨按照这样的思路解题
我们引入这样的例子
比如给一根绳围成一个矩形求在长和宽为多少时矩形面积最大
那么可求得当长和宽相等时矩形面积最大长和宽之间的差距为0
那么用同样的思路有n个格需要清扫有k个机器人我们希望每个机器人能够平分任务而且尽量不重复清扫这样消耗时间是最短的消耗时间设为x
所以这里用二分查找计算出最小值
剩下的思路不好表达不妨结合代码来说
total代表前n-1个机器人已经清扫到的格数这里我们把机器人的任务设定为需要清扫完右边的并且在下一个机器人左边的方格
首先目前这个机器人根据目前的x值能够到达total位置这个机器人能够弥补上一个机器人没有清扫的格数这个是必须要满足的条件如果下一个机器人不能够填补上一个机器人留下的漏洞那么漏洞会越积越大这肯定是不行的
然后满足了这个条件后就需要优中选优这里我们分为两种情况讨论
1.如果前一个机器人能够完成自己的任务即目前这个机器人不用往左边清扫了total直接加上目前的x值再减一就是已经清扫的范围
2.如果前一个机器人不能完成自己的任务那么需要先完成前一个机器人剩下的任务然后再开始自己的工作
代码如下
#include bits/stdc.h
using namespace std;
const int maxn1e57;
int n,m;
int robot_list[maxn];bool check(int x)
{int total0;for(int i0;im;i){if(robot_list[i]-xtotal)//能够到达total位置弥补前面一个机器人留的未清扫区域 {if(robot_list[i]total) totalrobot_list[i]x-1;else totalx;//左边没扫完 }else return false; //不能够到达total位置不能弥补前面一个机器人留的未清扫区域直接失败 }return totaln;//这种情况下才成立返回true
}
int main()
{cinnm;for(int i0;im;i){cinrobot_list[i];}sort(robot_list,robot_listm);//排序int left1,rightn,middle0,ans0;while(leftright){middle(rightleft)/2;if(check(middle)){rightmiddle-1;ansmiddle;}else{ leftmiddle1; } } cout(ans-1)*2endl;return 0;
}
