【洛谷】P3853 路标设置
原题链接:https://www.luogu.com.cn/problem/P3853
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述
2. 思路分析
整体思路:二分答案
由题意知,公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标,使得公路的“空旷指数”最小。也就是满足最大值最小。我们就自然想到可以二分答案。
定义三个变量L,n,k分别表示公路的长度,原有路标的数量,以及最多可增设的路标数量。开一个数组a,数组的第i个元素a[i]表示原有路标与起点的距离。
我们这里又开了一个差值数组s,令s[i]=a[i]-a[i-1],这样就可以用数组s表示原有的两个相邻路标的距离。
令左边界l=0,右边界r=L。
套用二分模板,mid=(l+r)>>1。主要就是要写一个check()函数,设check()函数的形参为x,将mid传入x。我们定义一个cnt变量用于记录新增的路标数量,遍历s[i]数组,如果s[i]>x,我们就要新增一个路标(cnt++),同时我们判断剩余部分(s[i]-x)的长度和x的关系,如果剩余部分的长度比x大,我们就继续插路标(cnt++),直到num<=x。
for循环结束后,我们判断一下cnt(新增路标数量)和k(最多可增设的路标数量),如果cnt<=k,return true。否则return false。
3. 代码实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
ll a[N], s[N], L, n, k, maxx;bool check(int x) {ll cnt = 0;for (int i = 1; i <= n; i++) {if (s[i] > x) {cnt++;int num = s[i] - x;while (num > x) {cnt++;num -= x;}}}if (cnt <= k) return true;else return false;
}int main() {cin >> L >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];s[i] = a[i] - a[i - 1];}int l = 0, r = L;while (l + 1 < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid;}cout << r << endl;return 0;
}

相关文章:
【洛谷】P3853 路标设置
原题链接:https://www.luogu.com.cn/problem/P3853 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 整体思路:二分答案 由题意知,公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标&…...
探索图像数据中的隐藏信息:语义实体识别和关系抽取的奇妙之旅
探索图像数据中的隐藏信息:语义实体识别和关系抽取的奇妙之旅 1. 简介 1.1 背景 关键信息抽取 (Key Information Extraction, KIE)指的是是从文本或者图像中,抽取出关键的信息。针对文档图像的关键信息抽取任务作为OCR的下游任务,存在非常…...
Gradle问题处理
目录 一、依赖搜索问题1.1 、Gradle不在本地 Maven 存储库中进行搜索一、依赖搜索问题 1.1 、Gradle不在本地 Maven 存储库中进行搜索 场景 build.gradle文件: buildscript {repositories {mavenLocal()google()mavenCentral()}dependencies...
架构:C4 Model
概念 C4说穿了就是几个要素:关系——带箭头的线、元素——方块和角色、关系描述——线上的文字、元素的描述——方块和角色里的文字、元素的标记——方块和角色的颜色、虚线框(在C4里面虚线框的表达力被极大的限制了,我觉得可以给虚线框更大…...
数据结构学习系列之顺序表的两种修改方式
方式1:根据顺序表中数据元素的位置进行修改,代码如下:示例代码: int modify_seq_list_1(list_t *seq_list,int pos, int data){if(NULL seq_list){printf("入参为NULL\n");return -1;}if( pos < 0 || pos > seq…...
React:props说明
props是只读对象(readonly) 根据单项数据流的要求,子组件只能读取props中的数据,不能进行修改props可以传递任意数据 数字、字符串、布尔值、数组、对象、函数、JSX import FileUpdate from ./FileUpdate; export default class …...
Can‘t connect to local MySQL server through socket ‘/tmp/mysql.sock‘
最近在用django框架开发后端时,在运行 $python manage.py makemigrations 命令时,报了以上错误,错误显示连接mysql数据库失败,查看了mysql数据库初始化配置文件my.cnf,我的mysql.sock文件存放路径配置在了/usr/local…...
C++的单例模式
忘记之前有没有写过单例模式了。 再记录一下: 我使用的代码: #ifndef SINGLETON_MACRO_HPP #define SINGLETON_MACRO_HPP#define SINGLETON_DECL(class_name) \ public: \static class_name& instance() { \static class_name s_instance; \return …...
Spring Boot 中 Nacos 配置中心使用实战
官方参考文档 https://nacos.io/zh-cn/docs/quick-start-spring-boot.html 本人实践 1、新建一个spring boot项目 我的spirngboot版本为2.5.6 2、添加一下依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-…...
学生管理系统VueAjax版本
学生管理系统VueAjax版本 使用Vue和Ajax对原有学生管理系统进行优化 1.准备工作 创建AjaxResult类,对Ajax回传的信息封装在对象中 package com.grg.Result;/*** Author Grg* Date 2023/8/30 8:51* PackageName:com.grg.Result* ClassName: AjaxResult* Descript…...
迭代器模式简介
概念: 迭代器模式是一种行为型设计模式,它提供了一种访问集合对象元素的方法,而无需暴露其内部表示。通过使用迭代器,可以按照特定顺序遍历集合中的元素。 特点: 将遍历和具体集合分离,使得能够独立地改…...
四方定理c++题解
题目描述 四方定理是数论中著名的一个定理,指任意一个自然数都可以拆成四个自然数的平方之和。例如: 251^22^22^24^2 对 25来说,还有其他方案: 250^20^23^24^2 以及 250^20^20^25^2 给定一个自然数 n ,请输出 n…...
ZDH-权限模块
本次介绍基于ZDH v5.1.2版本 目录 项目源码 预览地址 安装包下载地址 ZDH权限模块 ZDH权限模块-重要名词划分 ZDH权限模块-菜单管理 ZDH权限模块-角色管理 ZDH权限模块-用户配置 ZDH权限模块-权限申请 项目源码 zdh_web: GitHub - zhaoyachao/zdh_web: 大数据采集,抽…...
漏洞修复:在应用程序中发现不必要的 Http 响应头
描述 blablabla描述,一般是在返回的响应表头中出现了Server键值对,那我们要做的就是移除它,解决方案中提供了nginx的解决方案 解决方案 第一种解决方案 当前解决方案会隐藏nginx的版本号,但还是会返回nginx字样,如…...
什么是mkp勒索病毒,中了mkp勒索病毒怎么办?勒索病毒解密数据恢复
mkp勒索病毒是一种新兴的计算机木马病毒,它以加密文件的方式进行勒索,对用户的计算机安全造成了严重威胁。本文将介绍mkp勒索病毒的特征、影响以及应对措施,以便读者更好地了解和防范这种病毒。 一、mkp勒索病毒的特征 加密文件:…...
db2迁移至oracle
1.思路 (1)用java连接数据库(2)把DB2数据导出为通用的格式如csv,json等(3)导入其他数据库,比如oracle,mongodb。这个方法自由发挥的空间比较大。朋友说他会用springboot…...
webpack学习使用
...
按钮控件之2---QComboBox 复选按钮/复选框控件
1、常用函数: comboBox->addItem("cxq"); //添加下拉选项 combobox->clear(); //清空下拉项comboBox->setCurrentIndex(0);//设置当前的索引 int currentlndex(): //返回当前项的序号,第一个项的序号…...
【数据分享】2006-2021年我国省份级别的燃气相关指标(免费获取\20多项指标)
《中国城市建设统计年鉴》中细致地统计了我国城市市政公用设施建设与发展情况,在之前的文章中,我们分享过基于2006-2021年《中国城市建设统计年鉴》整理的2006—2021年我国省份级别的市政设施水平相关指标、2006-2021年我国省份级别的各类建设用地面积数…...
C语言深入理解指针(非常详细)(二)
目录 指针运算指针-整数指针-指针指针的关系运算 野指针野指针成因指针未初始化指针越界访问指针指向的空间释放 如何规避野指针指针初始化注意指针越界指针不使用时就用NULL避免返回局部变量的地址 assert断言指针的使用和传址调用传址调用例子(strlen函数的实现&a…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...

