当前位置: 首页 > news >正文

扫地机器人(蓝桥杯C/C++)

题目描述

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

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

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

  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,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 maxn=1e5+7;
int n,m;
int robot_list[maxn];bool check(int x)
{int total=0;for(int i=0;i<m;i++){if(robot_list[i]-x<=total)//能够到达total位置,弥补前面一个机器人留的未清扫区域 {if(robot_list[i]<=total) total=robot_list[i]+x-1;else total+=x;//左边没扫完  }else return false; //不能够到达total位置,不能弥补前面一个机器人留的未清扫区域,直接失败 }return total>=n;//这种情况下才成立,返回true 
}
int main()
{cin>>n>>m;for(int i=0;i<m;i++){cin>>robot_list[i];}sort(robot_list,robot_list+m);//排序int left=1,right=n,middle=0,ans=0;while(left<=right){middle=(right+left)/2;if(check(middle)){right=middle-1;ans=middle;}else{ left=middle+1; } } cout<<(ans-1)*2<<endl;return 0;
}

相关文章:

扫地机器人(蓝桥杯C/C++)

题目描述 小明公司的办公区有一条长长的走廊&#xff0c;由 NN 个方格区域组成&#xff0c;如下图所示。 走廊内部署了 KK 台扫地机器人&#xff0c;其中第 ii 台在第 A_iAi​ 个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中&#xff0c;并将该区域清扫干净。…...

如何理解API?API 是如何工作的?(5分钟诠释)

大家可能最近经常听到 API 这个概念&#xff0c;那什么是API&#xff0c;它又有什么特点和好处呢&#xff1f; wiki 百科镇楼 …[APIs are] a set of subroutine definitions, protocols, and tools for building application software. In general terms, it’s a set of cle…...

PAT--1111 对称日

央视新闻发了一条微博&#xff0c;指出 2020 年有个罕见的“对称日”&#xff0c;即 2020 年 2 月 2 日&#xff0c;按照 年年年年月月日日 格式组成的字符串 20200202 是完全对称的。 给定任意一个日期&#xff0c;本题就请你写程序判断一下&#xff0c;这是不是一个对称日&a…...

前端纯函数和副作用概念,且在react上的体现详解

什么是纯函数 纯函数是这样一种函数&#xff0c;即相同的输入&#xff0c;永远会得到相同的输出的函数&#xff0c;而且没有任何可观察的副作用。 什么是副作用 副作用是在计算结果的过程中&#xff0c;系统状态的一种变化&#xff0c;或者与外部世界进行的可观察的交互。 个…...

转行软件测试3年了,听前辈说测试前途是IT里最low的,我慌了......

互联网行业的技术岗位一般分为研发、测试和运维&#xff0c;虽然前些年测试一直都不如研发岗位那么吃香。但现在随着国内对软件测试的重视&#xff0c;我国互联网企业对软件测试的需求在未来还将继续增大。听起来软件测试的就业形势一片大好&#xff0c;那么到底软件测试的发展…...

CNI 网络流量 5.1 Cilium 介绍和原理

文章目录简介安装组件和原理Cilium-agent初始化IPAMCNICilium cli 的使用bpfMap 的操作Cilium-agentEbpf简介 Cilium 是一个用于容器网络领域的开源项目&#xff0c;主要是面向容器而使用&#xff0c;用于提供并透明地保护应用程序工作负载&#xff08;如应用程序容器或进程&a…...

机加行业MES解决方案,助力企业打造数字化透明车间

机械加工行业的主要原材料占整个生产物料成本的95%~99%&#xff0c;以挖掘机为例&#xff0c;原材料有各种规格的钢板、焊丝、焊条、油漆以及各种气体等&#xff0c;其中主要原材料是钢板&#xff0c;占原材料比率的98%以上。 因此机械加工mes的原材料管理是机械加工行业信息化…...

C/C++每日一练(20230227)

目录 1. 按要求排序数组 ★ 2. Z 字形变换 ★★ 3. 下一个排列 ★★ 1. 按要求排序数组 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中&#xff0c;数字 1 的数目升序排序。 如果存在多个数字二进制中 1 的数目相同&#xff0c;则必须将它们按照数值大小…...

总结SpringBoot1.x迁移到2.x需要注意的问题

SpringBoot1.x和SpringBoot2.x版本差异化还是比较大的&#xff0c;有些三方依赖组件有些是基于2.0版本为标准升级的&#xff0c;当我们将项目由1.0升级到2.0时会出现依赖的方法不存在或方法错误&#xff0c;需要逐个去调整&#xff0c;下面总结了我们升级实践过程中遇到的一些问…...

Api接口小知识

应用程序接口API&#xff08;Application Programming Interface&#xff09;,是提供特定业务输出能力、连接不同系统的一种约定。这里包括外部系统与提供服务的系统&#xff08;中控系统&#xff09;或者后台不同的系统之间的交互点。包括外部接口、内部接口、内部接口有包括&…...

「JVM 高效并发」Java 协程

Java 语言抽象和隐藏了各种操作系统线程差异性的接口&#xff0c;这曾经是它区别于其他编程语言的一大优势&#xff0c;但在某些场景下&#xff0c;却已经出现了疲态&#xff1b; 文章目录1. 内核线程的局限2. 协程的复苏3. Java 的解决方案1. 内核线程的局限 在微服务架构中&…...

Web Spider案例 网洛者 第一题 JS混淆加密 - 反hook操作 练习(五)

文章目录一、资源推荐二、第一题 JS混淆加密 - 反hook操作2.1 过控制台反调试(debugger)2.2 开始逆向分析三、python具体实现代码四、记录一下&#xff0c;execjs调用混淆JS报错的问题总结提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、资源推荐 …...

前端基础之CSS扫盲

文章目录一. CSS基本规范1. 基本语法格式2. 在HTML引入CSS3. 选择器分类二. CSS常用属性1. 文本属性2. 文本格式3. 背景属性4. 圆角矩形和圆5. 元素的显示模式6. CSS盒子模型7. 弹性布局光使用HTML来写一个前端页面的话其实只是写了一个大体的框架, 整体的页面并不工整美观, 而…...

mysql组复制、mysql路由器、mysql的MHA高可用

文章目录前言一、mysql组复制1.实验机配置2.测试二、mysql路由器三、mysql之MHA高可用1.MHA概念1.创建一主两从集群2.MHA部署3.故障切换前言 一、mysql组复制 1.实验机配置 server1配置 首先停止数据库 [rootserver1 mysql]# /etc/init.d/mysqld stop Shutting down MySQL..…...

一篇搞懂springboot多数据源

好文推荐 https://zhuanlan.zhihu.com/p/563949762 mybatis 配置多数据源 参考文章 https://blog.csdn.net/qq_38353700/article/details/118583828 使用mybatis配置多数据源我接触过的有两种方式&#xff0c;一种是通过java config的方式手动配置两个数据源&#xff0c;…...

Verilog 数据类型和数组简介

在这篇文章将讨论 verilog 中最常用的数据类型&#xff0c;包括对数据表示&#xff0c;线网类型、变量类型&#xff0c;向量类型和数组的讨论。尽管 verilog 被认为是一种弱类型语言&#xff08;loosely typed&#xff09;&#xff0c;但设计者仍必须在 Verilog 设计中为每个端…...

【数据结构】时间复杂度和空间复杂度以及相关OJ题的详解分析

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录1.算法效率1.1 如何衡…...

31--Vue-前端开发-Vue语法

一、前端-Vue介绍 1.前端介绍 1、HTML(5)、CSS(3)、JavaScript(ES5、ES6):编写一个个的页面 ----> 给后端(PHP、Python、Go、Java) ----> 后端嵌入模板语法 ----> 后端渲染完数据 ----> 返回数据给前端 ----> 在浏览器中查看 2、Ajax的出现 -> 后台发送异…...

这份IC设计必读书单,值得所有IC设计工程师一看!

《综合与时序分析的设计约束》 作者&#xff1a;Sridhar Gangadharan 本书为集成电路时序约束设计的指南&#xff0c;指导读者通过指定的时序要求&#xff0c;充分发挥IC设计的性能。本书内容包括受时序约束的关键环节的设计流程、综合时序分析、静态时序分析和布局布线等。本书…...

Acwing 蓝桥杯 第一章 递归与递推

我上周在干什么&#xff0c;感觉我上周啥也没训&#xff0c;本来两天一次的vp也没v很寄啊&#xff0c;再这样下去真不行了先总结一下如何爆搜&#xff1a;先去确定好枚举的对象枚举的对象很重要&#xff01;&#xff01;这直接影响了复杂度然后就是去想递归树就好了一、确定状态…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...