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

【洛谷】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 路标设置

原题链接&#xff1a;https://www.luogu.com.cn/problem/P3853 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 整体思路&#xff1a;二分答案 由题意知&#xff0c;公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标&…...

探索图像数据中的隐藏信息:语义实体识别和关系抽取的奇妙之旅

探索图像数据中的隐藏信息&#xff1a;语义实体识别和关系抽取的奇妙之旅 1. 简介 1.1 背景 关键信息抽取 (Key Information Extraction, KIE)指的是是从文本或者图像中&#xff0c;抽取出关键的信息。针对文档图像的关键信息抽取任务作为OCR的下游任务&#xff0c;存在非常…...

Gradle问题处理

目录 一、依赖搜索问题1.1 、Gradle不在本地 Maven 存储库中进行搜索一、依赖搜索问题 1.1 、Gradle不在本地 Maven 存储库中进行搜索 场景 build.gradle文件: buildscript {repositories {mavenLocal()google()mavenCentral()}dependencies...

架构:C4 Model

概念 C4说穿了就是几个要素&#xff1a;关系——带箭头的线、元素——方块和角色、关系描述——线上的文字、元素的描述——方块和角色里的文字、元素的标记——方块和角色的颜色、虚线框&#xff08;在C4里面虚线框的表达力被极大的限制了&#xff0c;我觉得可以给虚线框更大…...

数据结构学习系列之顺序表的两种修改方式

方式1&#xff1a;根据顺序表中数据元素的位置进行修改&#xff0c;代码如下&#xff1a;示例代码&#xff1a; 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是只读对象&#xff08;readonly&#xff09; 根据单项数据流的要求&#xff0c;子组件只能读取props中的数据&#xff0c;不能进行修改props可以传递任意数据 数字、字符串、布尔值、数组、对象、函数、JSX import FileUpdate from ./FileUpdate; export default class …...

Can‘t connect to local MySQL server through socket ‘/tmp/mysql.sock‘

最近在用django框架开发后端时&#xff0c;在运行 $python manage.py makemigrations 命令时&#xff0c;报了以上错误&#xff0c;错误显示连接mysql数据库失败&#xff0c;查看了mysql数据库初始化配置文件my.cnf&#xff0c;我的mysql.sock文件存放路径配置在了/usr/local…...

C++的单例模式

忘记之前有没有写过单例模式了。 再记录一下&#xff1a; 我使用的代码&#xff1a; #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类&#xff0c;对Ajax回传的信息封装在对象中 package com.grg.Result;/*** Author Grg* Date 2023/8/30 8:51* PackageName:com.grg.Result* ClassName: AjaxResult* Descript…...

迭代器模式简介

概念&#xff1a; 迭代器模式是一种行为型设计模式&#xff0c;它提供了一种访问集合对象元素的方法&#xff0c;而无需暴露其内部表示。通过使用迭代器&#xff0c;可以按照特定顺序遍历集合中的元素。 特点&#xff1a; 将遍历和具体集合分离&#xff0c;使得能够独立地改…...

四方定理c++题解

题目描述 四方定理是数论中著名的一个定理&#xff0c;指任意一个自然数都可以拆成四个自然数的平方之和。例如&#xff1a; 251^22^22^24^2 对 25来说&#xff0c;还有其他方案&#xff1a; 250^20^23^24^2 以及 250^20^20^25^2 给定一个自然数 n &#xff0c;请输出 n…...

ZDH-权限模块

本次介绍基于ZDH v5.1.2版本 目录 项目源码 预览地址 安装包下载地址 ZDH权限模块 ZDH权限模块-重要名词划分 ZDH权限模块-菜单管理 ZDH权限模块-角色管理 ZDH权限模块-用户配置 ZDH权限模块-权限申请 项目源码 zdh_web: GitHub - zhaoyachao/zdh_web: 大数据采集,抽…...

漏洞修复:在应用程序中发现不必要的 Http 响应头

描述 blablabla描述&#xff0c;一般是在返回的响应表头中出现了Server键值对&#xff0c;那我们要做的就是移除它&#xff0c;解决方案中提供了nginx的解决方案 解决方案 第一种解决方案 当前解决方案会隐藏nginx的版本号&#xff0c;但还是会返回nginx字样&#xff0c;如…...

什么是mkp勒索病毒,中了mkp勒索病毒怎么办?勒索病毒解密数据恢复

mkp勒索病毒是一种新兴的计算机木马病毒&#xff0c;它以加密文件的方式进行勒索&#xff0c;对用户的计算机安全造成了严重威胁。本文将介绍mkp勒索病毒的特征、影响以及应对措施&#xff0c;以便读者更好地了解和防范这种病毒。 一、mkp勒索病毒的特征 加密文件&#xff1a;…...

db2迁移至oracle

1.思路 &#xff08;1&#xff09;用java连接数据库&#xff08;2&#xff09;把DB2数据导出为通用的格式如csv&#xff0c;json等&#xff08;3&#xff09;导入其他数据库&#xff0c;比如oracle&#xff0c;mongodb。这个方法自由发挥的空间比较大。朋友说他会用springboot…...

webpack学习使用

...

按钮控件之2---QComboBox 复选按钮/复选框控件

1、常用函数&#xff1a; comboBox->addItem("cxq"); //添加下拉选项 combobox->clear(); //清空下拉项comboBox->setCurrentIndex(0);//设置当前的索引 int currentlndex()&#xff1a; //返回当前项的序号&#xff0c;第一个项的序号…...

【数据分享】2006-2021年我国省份级别的燃气相关指标(免费获取\20多项指标)

《中国城市建设统计年鉴》中细致地统计了我国城市市政公用设施建设与发展情况&#xff0c;在之前的文章中&#xff0c;我们分享过基于2006-2021年《中国城市建设统计年鉴》整理的2006—2021年我国省份级别的市政设施水平相关指标、2006-2021年我国省份级别的各类建设用地面积数…...

C语言深入理解指针(非常详细)(二)

目录 指针运算指针-整数指针-指针指针的关系运算 野指针野指针成因指针未初始化指针越界访问指针指向的空间释放 如何规避野指针指针初始化注意指针越界指针不使用时就用NULL避免返回局部变量的地址 assert断言指针的使用和传址调用传址调用例子&#xff08;strlen函数的实现&a…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

机器学习的数学基础:线性模型

线性模型 线性模型的基本形式为&#xff1a; f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法&#xff0c;得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...