蓝桥杯第199题 扫地机器人 暴力优化 二分法 简单题 C++

题目

扫地机器人 - 蓝桥云课 (lanqiao.cn)icon-default.png?t=N7T8https://www.lanqiao.cn/problems/199/learning/?page=1&first_category_id=1&name=%E6%89%AB%E5%9C%B0%E6%9C%BA%E5%99%A8%E4%BA%BA

思路和解题方法

  1. 首先,通过cin语句输入了终点位置n和障碍物数量k。
  2. 使用一个数组a来存储k个障碍物的位置。
  3. 对障碍物位置进行排序,以便后续的二分搜索。
  4. 然后,定义了一个函数check,用于检查是否能够在给定的时间内到达终点。该函数采用二分搜索的思想。
  5. check函数中,首先初始化当前位置为起点0。然后遍历每一个障碍物:
    • 如果当前位置小于障碍物位置,则需要额外花费时间走过去,时间花费为(a[i] - pos - 1) * 2
    • 若剩余时间不足以到达当前障碍物,则返回false,表示无法在给定时间内到达终点。
    • 否则,更新当前位置为走过障碍物后的位置,即pos = a[i] + t / 2
  6. 当所有障碍物都走过后,判断当前位置是否小于终点位置n,若小于则返回false,表示无法在给定时间内到达终点;否则返回true,表示可以在给定时间内到达终点。
  7. 主函数使用二分搜索来找到最短时间。初始化二分搜索的左边界l为0,右边界r为2 * n。
  8. 在while循环中,计算中间值mid,并调用check函数判断是否能在mid时间内到达终点。
    • 若可以,则更新答案ans为mid,并将右边界r缩小为mid-1,继续搜索更短的时间。
    • 若不可以,则将左边界l扩大为mid+1,继续搜索更长的时间。
  9. 最终输出答案ans,即为最短时间到达终点的结果。

复杂度

        时间复杂度:

                O(log N * K)

        时间复杂度为O(logN * K),其中N为终点位置,K为障碍物数量。主要时间消耗在二分搜索中。

        空间复杂度

                O(K)

        空间复杂度为O(K),其中K为障碍物数量,因为需要使用一个数组来存储障碍物的位置。

c++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

int n, k, a[100005]; // 定义变量n(终点位置)、k(障碍物数量)、a数组存放k个障碍物的位置
int ans; // 存放最终答案

// 检查是否能够在给定的时间内到达终点
bool check(int time)
{
    int pos = 0; // 当前位置初始化为起点
    for(int i = 0; i < k; ++i) // 遍历每一个障碍物
    {
        int t = time; // t表示剩余时间
        if(pos < a[i]) // 如果当前位置小于障碍物位置
            t -= (a[i] - pos - 1) * 2; // 则需要额外花费时间走过去
        if(t < 0) // 如果剩余时间不足以到达当前障碍物
            return false; // 返回false,表示无法在给定时间内到达终点
        pos = a[i] + t / 2; // 更新当前位置为走过障碍物后的位置
    }
    if(pos < n) // 如果所有障碍物都走过后,仍未到达终点
        return false; // 返回false,表示无法在给定时间内到达终点
    return true; // 否则返回true,表示可以在给定时间内到达终点
}

int main()
{
    cin >> n >> k; // 输入终点位置n和障碍物数量k
    for(int i = 0; i < k; i++)
        cin >> a[i]; // 输入k个障碍物的位置
    sort(a, a + k); // 对障碍物位置进行排序
    int l = 0, r = 2 * n; // 初始化二分搜索的左右边界

    while(l <= r) // 二分搜索
    {
        int mid = l + (r - l) / 2; // 取中间值
        if(check(mid)) // 能够在mid时间内到达终点
            ans = mid, r = mid - 1; // 更新答案并缩小右边界
        else
            l = mid + 1; // 否则扩大左边界
    }

    cout << ans << endl; // 输出答案
    return 0;
}

未优化的代码 暴力 time从0~2*n

	for(int i = 0;i<=2*n;i++)
    {
        if(check(i)){
            ans = i;
            break;
        }
    }

时间对比

我的文档里面也有许多二分(双指针)题目,可供大家参考作答。

双指针_冷yan~的博客-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/jgk666666/category_12470278.html

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/202330.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

element-plus el-dialog 弹窗隐藏遮罩并且可以控制弹窗后的元素、点击、滚动、其他事件操作等

场景 el-dialog 隐藏遮罩并且可以控制弹窗后的元素、点击、滚动、其他事件操作&#xff0c;比如一个弹窗打开了&#xff0c;我要能控制弹窗后面的滚动、点击等等一系列事件。 修改方法 首先我们需要隐藏弹窗遮罩 :modal"false"&#xff0c;并且给 el-dialog 弹窗…

C语言基础--#if与#endif

目录 一、C语言中的 #if()和 #end if 用法 1. #if 表达式 程序段 #endif 形式 2. #ifdef标示符 标识符 #endif 形式 3. #if 0/ #if 1 #endif 形式 4. \可用于一行的结尾&#xff0c;表示本行与下一行连接起来 二、xTaskCreate函数 三、指针相关…

Java容器合集

目录 浅谈 Array数组 初始化(动与静) 动态初始化 静态初始化 CRUD 增 查 索引取值 遍历 改 删 走进底层 栈与堆 一个数组的诞生 多数组 避坑指南 索引越界 空指针异常 小试牛刀 Collection List部落 介绍和特点 方法 ArrayList 介绍 方法 遍历 Li…

docker搭建node环境开发服务器

docker搭建node环境开发服务器 本文章是我自己搭建node环境开发服务器的过程记录&#xff0c;不一定完全适用所有人。根据个人情况&#xff0c;按需取用。 命名项目路径 为了方便cd到项目路径&#xff0c;将项目路径重命名&#xff0c;方便输入。 vim /etc/profile # 修改p…

创建Asp.net MVC项目Ajax实现视图页面数据与后端Json传值显示

简述回顾 继上篇文章创建的mvc传值这里说明一下Json传值。在mvc框架中&#xff0c;不可避免地会遇到前台传值到后台&#xff0c;前台接收后台的值的情况&#xff08;前台指view&#xff0c;后台指controller&#xff09;&#xff0c;有时只需要从控制器中返回一个处理的结果&a…

Steps步骤条(antd-design组件库)简单用法

1.Steps步骤条 引导用户按照流程完成任务的导航条。 2.何时使用 当任务复杂或者存在先后关系时&#xff0c;将其分解成一系列步骤&#xff0c;从而简化任务。 组件代码来自&#xff1a; 步骤条 Steps - Ant Design 3.本地验证前的准备 参考文章【react项目antd组件-demo:hello-…

用bat制作图片马——一句话木马

效果图 代码 ECHO OFF TITLE PtoR MODE con COLS55 LINES25 color 0A:main cls echo.当前时间&#xff1a;%date% %time% echo.欢迎使用图片马制作工具 echo.请确保图片和php在同一路径下 echo.echo 请将图像文件拖放到此窗口并按 Enter&#xff1a; set /p "imagefile&q…

项目demo —— GPT 聊天机器人

本文介绍我的开源项目 TelegramChatBot&#xff0c;这是一个基于 OpenAI GPT API 开发的 telegram 机器人&#xff0c;具有多模态交互能力&#xff0c;求 star&#xff01;感谢大家&#xff01;在 telegram jokerController_bot 立即体验&#xff01;欢迎对 GPT 应用开发或对 t…

SQL server-excel数据追加到表

参考文章&#xff1a;SQL server 2019 从Excel导入数据_mssql2019 导入excel数据-CSDN博客 将excel数据导入到SQL server数据库的详细过程 注意&#xff1a;第一行数据默认为数据库表中的字段&#xff0c;所以这个必须要有&#xff0c;否则无法映射导入 问题1&#xff1a;ADD…

如何使用阿里云虚拟主机和域名设置网站?

本文档将向您展示如何使用阿里云虚拟主机来设置一个新网站&#xff0c;并完成一个域名。如果您按照此处的步骤操作&#xff0c;您将启动并运行一个新网站&#xff0c;可以使用您选择的名称在全球范围内访问&#xff0c;并托管在阿里云平台上。 本文档假设您已经拥有有效的阿里…

Python爬虫遇到重定向URL问题时如何解决?

什么是重定向 重定向是指当用户请求一个URL时&#xff0c;服务器返回一个中断请求的URL的响应。这种情况通常发生在网站对URL进行了修改或者重定向到其他页面的情况下。其中&#xff0c;如果处理不当开发&#xff0c;可能会导致爬虫无法获取所需的数据&#xff0c;从而影响爬虫…

基于SSM的仓库管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

CentOS7安装RabbitMQ

服务器系统版本&#xff1a;CentOS7 安装RabbitMq版本&#xff1a;3.7.18 将此安装包目录下的两个文件上传到服务/usr/local/rabbitmq中备用。 安装Erlang依赖包 rpm -ivh erlang-22.0.7-1.el7.x86_64.rpm安装RabbitMQ安装包(需要联网) yum install -y rabbitmq-server-3.7.1…

Message全局提示(antd-design组件库)简单用法

1.Message全局提示 全局展示操作反馈信息。 2.何时使用 可提供成功、警告和错误等反馈信息。 顶部居中显示并自动消失&#xff0c;是一种不打断用户操作的轻量级提示方式。 组件代码来自&#xff1a; 全局提示 Message - Ant Design 3.本地验证前的准备 参考文章【react项目ant…

【LeetCode】101. 对称二叉树

101. 对称二叉树 难度&#xff1a;简单 题目 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#…

Java高级技术(注解)

一&#xff0c;注解 二&#xff0c;案例 三&#xff0c;注解原理 四&#xff0c;元注解 五&#xff0c;案例 六&#xff0c;解析注解 七&#xff0c;案例

本地部署GPT的实战方案

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…

C++面向对象复习笔记暨备忘录

C指针 指针作为形参 交换两个实际参数的值 #include <iostream> #include<cassert> using namespace std;int swap(int *x, int* y) {int a;a *x;*x *y;*y a;return 0; } int main() {int a 1;int b 2;swap(&a, &b);cout << a << &quo…

多模块项目打包部署

目录结构 这些模块间相互依赖&#xff0c;打包的时候打父模块&#xff0c;就是带root的这个 先clean&#xff0c;再package&#xff0c;就跟一般的项目一样了。 有可能遇到报错Failed to execute goal org.apache.maven.plugins:maven-surefire-plugin:2.22.2:test&#xff…

springboot基础配置及maven运行

目录 1、spring快速开始&#xff1a; 2、通过idea工具打开导入包 3、maven打包 1、springboot快速开始&#xff1a; 环境依赖&#xff1a;jdk17 Spring | Quickstart spring初始化包下载&#xff1a; 点击generate&#xff0c;下载包 2、通过idea工具打开导入包 我之前写了…