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

扫地机器人(二分算法+贪心算法)

1.  if(robot[i]-len<=sweep)这个代码的意思是——如果机器人向左移动len个长度后,比现在sweep的位置(现在已经覆盖的范围)还要靠左,就是覆盖连续不起来,呢么这个len就是有问题的,退出函数,再继续循环。

2.  显然当每个机器人清扫的范围相同时,所用时间最小,所以这时候可以想到用二分算法,check条件(判断条件)是每个清扫范围都能被扫到。

 输入:

10 3

5

2

10

输出:6

输出机器人清扫玩完所有区域至少花费的时间.

 

#include<bits/stdc++.h>using namespace std;int robot[100010];int n,k;
bool check(int len){int sweep=0;int i;for(i=1;i<=k;i++){if(robot[i]-len<=sweep){if(robot[i]<=sweep){sweep=robot[i]+len-1;}else{sweep=sweep+len;}}else{return 0;}}return sweep>=n;
}
int main()
{scanf("%d",&n);scanf("%d",&k);int i;for(i=1;i<=k;i++){scanf("%d",&robot[i]);}sort(robot+1,robot+k+1);int m,l=0,r=n,ans;while(l<=r){m=(r+l)/2;if(check(m)){r=m-1;ans=m;}else{l=m+1;}}printf("%d",(ans-1)*2);return 0;
}

 3.if(robot[i]<=sweep)

这个代码的意思是robot[i]此时所处的位置在已经被上一个机器人清扫过的位置了,所以此时sweep的值为robot[i]向右走的len然后减去1(减去robot起始位置)

否则的话robot[i]此时所处的位置为上一个机器人还未清扫过的位置,此时这个机器人会优先往左清扫,即sweep=sweep+len;

4.sort(robot+1,robot+k+1);

sort函数的两个参数是排序的起点和终点位置,robot加1的原因是数组是从1开始排列的,而不是从0开始排列的。

5.if(check(m)){

r=m-1}是因为如果此时的m满足清扫的条件,呢么接下来应该找比m更小的范围(对应更小的时间)即往m的左区间更小的数去找。即r=m-1。

注:代码来自lanqiao6628158049

相关文章:

扫地机器人(二分算法+贪心算法)

1. if(robot[i]-len<sweep)这个代码的意思是——如果机器人向左移动len个长度后&#xff0c;比现在sweep的位置&#xff08;现在已经覆盖的范围&#xff09;还要靠左&#xff0c;就是覆盖连续不起来&#xff0c;呢么这个len就是有问题的&#xff0c;退出函数&#xff0c;再…...

Unity中创建Ultraleap 3Di交互项目

首先&#xff0c;创建新的场景 1、创建一个空物体&#xff0c;重命名为【XP Leap Provider Manager】&#xff0c;并在这个空物体上添加【XR Leap Provider Manager】 在物体XP Leap Provider Manager下&#xff0c;创建两个子物体Service Provider(XR)和Service Provider(…...

【Matlab】音频信号分析及FIR滤波处理——凯泽(Kaiser)窗

一、前言 1.1 课题内容: 利用麦克风采集语音信号(人的声音、或乐器声乐),人为加上环境噪声(窄带)分析上述声音信号的频谱,比较两种情况下的差异根据信号的频谱分布,选取合适的滤波器指标(频率指标、衰减指标),设计对应的 FIR 滤波器实现数字滤波,将滤波前、后的声音…...

C数据类型

目录 1. 数据类型分类 2. 整数类型 3. 浮点类型 4. void 类型 5. 类型转换 1. 数据类型分类 在 C 语言中&#xff0c;数据类型指的是用于声明不同类型的变量或函数的一个广泛的系统。变量的类型决定了变量存储占用的空间&#xff0c;以及如何解释存储的位模式。 C 中…...

JAVA和Go的不解之缘

JAVA和Go的不解之缘 Java和Go是两种不同的编程语言&#xff0c;它们在语法、特性和设计理念上存在一些明显的异同之处。 1. 语法和特性&#xff1a; Java是一种面向对象的语言&#xff0c;而Go则是一种面向过程的语言。Java拥有类、继承、接口等传统的面向对象特性&#xff…...

(免费领源码)java#SSM#MySQL汽车车辆管理系统68424-计算机毕业设计项目选题推荐

摘 要 科技进步的飞速发展引起人们日常生活的巨大变化&#xff0c;电子信息技术的飞速发展使得电子信息技术的各个领域的应用水平得到普及和应用。信息时代的到来已成为不可阻挡的时尚潮流&#xff0c;人类发展的历史正进入一个新时代。在现实运用中&#xff0c;应用软件的工作…...

25考研每日的时间安排

今天要给大家分享一下25考研每日的时间安排。 没有完美的计划&#xff0c;只有合适的计划。 仅供参考 很多人说复习不要只看时长而是要看效率&#xff0c;所以学多长时间不重要&#xff0c;重要的高效率完成任务。 完美的计划 这个计划看起来很完美&#xff0c;从早到晚有学习…...

小程序直播项目搭建

项目功能&#xff1a; 登录实时聊天点赞功能刷礼物取消关注用户卡片直播带货优惠券直播功能 项目启动&#xff1a; 1 小程序项目创建与配置&#xff1a; 第一步 需要登录小程序公众平台的设置页面进行配置&#xff1a; 首先需要是企业注册的才可以个人不能开通直播功能。服务类…...

《Python 简易速速上手小册》第10章:Python 项目实战(基于最新版 Python3.12 编写)

注意&#xff1a;本《Python 简易速速上手小册》 核心目的在于让零基础新手「快速构建 Python 知识体系」 文章目录 <mark >注意&#xff1a;本《Python 简易速速上手小册》<mark >核心目的在于让零基础新手「快速构建 Python 知识体系」 10.1 项目规划和结构10.1…...

防御保护第六天笔记

一、防火墙的用户认证 用户、行为、流量 --- 上网行为管理三要素 防火墙管理员登录认证的作用有两点&#xff1a;检验身份的合法性&#xff0c;划分身份权限 用户认证 --- 上网行为管理的一部分 用户认证分类有以下三类&#xff1a; 1、上网用户认证 --- 三层认证 --- 所有的…...

【yaml 文件使用】pytest+request 框架中 yaml 配置文件使用

又来进步一点点~~ 背景&#xff1a;最近在学习pytestrequest框架写接口测试自动化&#xff0c;使用yaml文件配置更方便管理用例中的数据&#xff0c;这样更方便 yaml 介绍&#xff1a; 什么是 yaml 文件&#xff1a;YAML 是 “YAML Ain’t a Markup Language”&#xff08;Y…...

浅析Redis②:命令处理之epoll实现(中)

写在前面 Redis作为我们日常工作中最常使用的缓存数据库&#xff0c;其重要性不言而喻&#xff0c;作为普通开发者&#xff0c;我们在日常开发中使用Redis&#xff0c;主要聚焦于Redis的基层数据结构的命令使用&#xff0c;很少会有人对Redis的内部实现机制进行了解&#xff0c…...

react如果创建了类似于 Icketang元素,那么该如何实现 Icketang类

要实现一个类似于 "Icketang" 的类&#xff0c;首先需要考虑该类的属性和方法。根据上下文&#xff0c;可以假设 "Icketang" 是一个卡片或票据类&#xff0c;可以包含以下属性和方法&#xff1a; 属性&#xff1a; card_number&#xff1a;卡片编号amoun…...

「数字化转型」企业架构:成功业务转型的关键

在麦肯锡最近的一篇文章中&#xff0c;他们雄辩地论证了企业架构对数字转型的重要性。但他们也对实践状况提出了一些重要的批评。为了真正有效地支持数字转型&#xff0c;许多企业架构实践需要改变他们的行为。 一些EA实践首先关注的是详细记录企业的当前状态。这通常是我们在许…...

AI开启手机摄影新时代:三星Galaxy S24 Ultra影像解读

在全球科技领域&#xff0c;生成式AI无疑是当前最为炙手可热的亮点&#xff0c;不少行业专家和业界领袖都纷纷预言&#xff0c;生成式AI技术必将重塑千行百业。 那么是否有人想过&#xff0c;如果生成式AI技术被应用在智能手机上&#xff0c;又会带来怎样翻天覆地的变革&#x…...

Linux ---- Shell编程之函数与数组

目录 一、函数 1、函数的基本格式 2、查看函数列表 3、删除函数 4、函数的传参数 5、函数返回值 实验&#xff1a; 1.判断输入的ip地址正确与否 2. 判断是否为管理员用户登录 6、函数变量的作用范围 7、函数递归&#xff08;重要、难点&#xff09; 实验&#xff1…...

Python系列(9)—— 比较运算符

在Python中&#xff0c;比较运算符用于比较两个值的大小关系&#xff0c;如等于、不等于、大于、小于等。这些运算符可以帮助我们进行各种比较操作&#xff0c;并返回布尔值&#xff08;True或False&#xff09;。下面我们将详细介绍Python中的比较运算符。 等于运算符&#x…...

uni-app h5对接 thinkphp5接口跨域

uni-app h5对接 thinkphp5接口跨域 问题描述 请求接口 提示 Access to XMLHttpRequest at http://******* from origin http://localhost:8091 has been blocked by CORS policy: Response to preflight request doesnt pass access control check: It does not have HTTP o…...

react-jss书写样式

目录 react-jss的使用 react-jss的使用 实现组件化样式、动态样式、避免样式冲突 npm install react-jss yarn add react-jss// 使用 import React from react; import { createUseStyles } from react-jss;const useStyles createUseStyles({myButton: {color: green,margi…...

Oracle PL/SQL Programming 第3章:Language Fundamentals 读书笔记

总的目录和进度&#xff0c;请参见开始读 Oracle PL/SQL Programming 第6版 每种语言&#xff08;无论是人类语言还是计算机语言&#xff09;都有语法、词汇和字符集。 为了使用该语言进行交流&#xff0c;您必须学习管理其使用的规则。 我们许多人对学习新的计算机语言持谨慎…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...