【洛谷】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…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

