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

news/2024/2/29 3:55:33

题目

扫地机器人 - 蓝桥云课 (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和障碍物数量kfor(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; // 更新答案并缩小右边界elsel = 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

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

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

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


https://www.xjx100.cn/news/3118852.html

相关文章

mac安装homebrew/brew遇到443

文章目录 问题描述解决方法方法一方法二 参考文献 问题描述 brew 全称Homebrew 是Mac OSX上的软件包管理工具 想在mac终端安装&#xff0c;运行网上提供的指令 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)&quo…

智能AI系统ChatGPT网站系统源码+Midjourney绘画+支持DALL-E3文生图,支持最新GPT-4-Turbo模型

一、AI创作系统 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI…

每日一题(LeetCode)----哈希表--两数之和

每日一题(LeetCode)----哈希表–两数之和 1.题目&#xff08;1. 两数之和&#xff09; 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答…

技术类知识汇总(二)

在自己日常学习javaweb的过程中&#xff0c;做的一些笔记和总结&#xff0c;汇总如下&#xff1a; Springboot项目的静态资源(html&#xff0c;css&#xff0c;js等前端资源)默认存放目录为&#xff1a;classpath:/static classpath:/public classpath:/resources"三层架…

AI搜索相关性在网站和APP上的应用

设定场景&#xff1a;您在寻找一件新衣服&#xff0c;所以在浏览最喜欢的网店。您跳到搜索栏上&#xff0c;输入您要找的东西。您期待出现什么结果&#xff1f; 高度准确、相关和即时的结果。 无论在什么网站上搜索&#xff0c;寻找什么&#xff0c;甚至在打错字或使用了错误的…

第十四章 算法和数据结构

Python基础、函数、模块、面向对象、网络和并发编程、数据库和缓存、 前端、django、Flask、tornado、api、git、爬虫、算法和数据结构、Linux、设计题、客观题、其他 第十四章 算法和数据结构 1. 顺序表、链表的区别及应用场景。 顺序表&#xff08;Sequential List&#xf…

DELETE 请求,如何通过ajax进行发送

基本的 DELETE 请求概念 DELETE 请求用于向服务器发送删除资源的请求。它是 RESTful API 中的一个重要方法&#xff0c;用于删除指定的资源。 在 Axios 中&#xff0c;发送 DELETE 请求需要指定目标 URL&#xff0c;并可选地传递一些参数&#xff0c;例如请求头、请求体等。DE…

CE认证关于电动滑板车安全标准EN17128和电动自行车EN15194电磁兼容测试解析

本标准适用于有或没有自平衡系统的全部或部分由自给式电源供电的个人轻型电动汽车&#xff0c;除无人值守站值守站租用的电动汽车外。自平衡系统完全或部分由最高100VDC电池电压的独立电源供电&#xff0c;并配备或无输入电压高达240VAC的集成电池充电器。该标准规定了与个人轻…