【二分+滑动窗口优化DP】CF883 I
Problem - 883I - Codeforces
题意:


思路:
首先,要让最大值最小,很显然要二分
那么就相当于有了一个极差的限制,看能不能分组,每组至少m个元素
那么就是考虑分段DP,直接n^2很容易写
但是n <= 3e5,需要优化一下
注意到分段DP的左端点 L 是在一个区间内的,那么我们就去维护这个区间,即滑动窗口优化DP
Code:
(模仿了一下Jiangly的码风)
#include <bits/stdc++.h>using i64 = long long;using namespace std;const int N = 3e5 + 10;int n, m;int a[N];bool check(int x) {vector<int> dp(n + 1, 0);dp[0] = 1;int pl = 1, pr = 1;for (int i = 1; i <= n ;i++) {while(a[i] - a[pl] > x) pl ++;pr = i + 1 - m;for(int j = pl; j <= pr; j++) {if(dp[j - 1]) {dp[i] = 1;break;}else {pl ++;}}}return dp[n];
}
void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + 1 + n);int l = 0, r = a[n] - a[1];int ans = 0;while (l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;r = mid - 1;}else {l = mid + 1;}}cout << ans << "\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--) {solve();}return 0;
}
相关文章:
【二分+滑动窗口优化DP】CF883 I
Problem - 883I - Codeforces 题意: 思路: 首先,要让最大值最小,很显然要二分 那么就相当于有了一个极差的限制,看能不能分组,每组至少m个元素 那么就是考虑分段DP,直接n^2很容易写 但是n …...
4.netty源码分析
1.pipeline调用handler的源码 //pipeline得到双向链表的头,next到尾部, 2.心跳源码 主要分析IdleStateHandler3个定时任务内部类 //考虑了网络传输慢导致出站慢的情况 //超时重新发送,然后关闭 ReadTimeoutHandler(继承IdleStateHandler 直接关闭连接)和WriteTimeoutHandler(继…...
性能优化点
Arts and Sciences - Computer Science | myUSF 索引3层(高度为3)一般对于数据库地址千万级别的表 大于2000万的数据进行分库分表存储 JVM整体结构及内存模型 JVM调优:主要为减少FULL GC的执行次数或者减少FULL GC执行时间 Spring Boot程序…...
leetcode301. 删除无效的括号(java)
删除无效的括号 leetcode301. 删除无效的括号题目描述暴力搜索 剪枝代码演示 回溯算法 leetcode301. 删除无效的括号 难度 困难 https://leetcode.cn/problems/remove-invalid-parentheses/description/ 题目描述 给你一个由若干括号和字母组成的字符串 s ,删除最小…...
快速制作美容行业预约小程序
随着科技的不断进步,移动互联网的快速发展,小程序成为了很多行业迅速发展的利器。对于美容行业来说,一款美容预约小程序不仅可以方便用户进行预约,还可以提升美容店铺的服务质量和管理效率。下面,我们来介绍一下如何快…...
Golang之路---03 面向对象——结构体
结构体 结构体定义 在之前学过的数据类型中,数组与切片,只能存储同一类型的变量。若要存储多个类型的变量,就需要用到结构体,它是将多个任意类型的变量组合在一起的聚合数据类型。 每个变量都成为该结构体的成员变量。 可以理…...
【网络编程】poll
主旨思想 用一个结构体记录文件描述符集合,并记录用户态状态和内核态状态 函数说明 概览 #include <poll.h> struct pollfd { int fd; /* 委托内核检测的文件描述符 */ short events; /* 委托内核检测文件描述符的什么事件 */ short revents; /* 文件描述…...
配置VS Code 使其支持vue项目断点调试
起因 每个应用,不论大小,都需要理解程序是如何运行失败的。当我们写的程序没有按照自己写的逻辑走的时候,我们就会逐步一一排查问题。在平常开发过程中我们可能会借助 console.log 来排查,但是现在我们可以借助 VS Code 断点来调试项目。 前…...
第一百零一回 如何在组件树之间共享数据
文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了"如何实现文件存储"相关的内容,本章回中将介绍 如何实现组件之间共享数据。闲话休提,让我们一起Talk Flutter吧。 概念介绍 数据共享是程序中常用的功能,本章回介绍如何…...
Golang进阶学习
Golang进阶学习 视频地址:https://www.bilibili.com/video/BV1Pg41187AS?p35 1、包 1.1、包的引入 使用包的原因: 我们不可能把所有函数放在同一个源文件中,可以分门别类的放在不同的文件中 解决同名问题,同一个文件中不可以…...
【Linux】常用的基本指令
👦个人主页:Weraphael ✍🏻作者简介:目前正在学习c和算法 ✈️专栏:Linux 🐋 希望大家多多支持,咱一起进步!😁 如果文章有啥瑕疵,希望大佬指点一二 如果文章对…...
栈溢出几种情况及解决方案
一、局部数组过大。当函数内部的数组过大时,有可能导致堆栈溢出。 二、递归调用层次太多。递归函数在运行时会执行压栈操作,当压栈次数太多时,也会导致堆栈溢出。 三、指针或数组越界。这种情况最常见,例如进行字符串拷贝&#…...
go 内存分配
关注 go 语言内存分配策略,主要是想了解 go 的性能。申请不同大小的内存,性能开销是有差别的,申请内存越大,耗时也越久,性能也越差。 内存分配 参考 Go1.17.13 版本源码,从内存分配大小上区分了 tiny、sm…...
Maven pom.xml文件中build,plugin标签的具体使用
<build> 标签 <build> 标签是 pom.xml 文件中一个重要的标签,用于配置 Maven 项目的构建过程。在 <build> 标签下,可以配置构建相关的设置,包括源代码目录、输出目录、插件配置等。 以下是 <build> 标签的详细使用方…...
批量插入数据、MVC三层分离
八、批量插入数据 1、使用Statement() 2、使用PreparedStatement() 3、使用批量操作API 4、优化 九、MVC三层分离...
【IMX6ULL驱动开发学习】21.Linux驱动之PWM子系统(以SG90舵机为例)
1.设备树部分 首先在 imx6ull.dtsi 文件中已经帮我们定义好了一些pwm的设备树节点,这里以pwm2为例 pwm2: pwm02084000 {compatible "fsl,imx6ul-pwm", "fsl,imx27-pwm";reg <0x02084000 0x4000>;interrupts <GIC_SPI 84 IRQ_TYP…...
el-cascader级联选择器加载远程数据、默认开始加载固定条、可以根据搜索加载远程数据。
加载用户列表分页请求、默认请求20条数据。想添加远程搜索用户功能。原有的方法filter-method不能监听到输入清空数据的时候。这样搜索完无法返回默认的20条数据。直接监听级联选择的v-model绑定的值是无法检测到用户自己输入的。 解决思路: el-cascader 没有提供…...
大数据技术之Clickhouse---入门篇---SQL操作、副本
星光下的赶路人star的个人主页 积一勺以成江河,累微尘以崇峻极 文章目录 1、SQL操作1.1 Insert1.2 Update 和 Delete1.3 查询操作1.4 alter操作1.5 导出数据 2、副本2.1 副本写入流程2.2 配置步骤 1、SQL操作 基本上来说传统关系型数据库(以 MySQL 为例…...
【Rust 基础篇】Rust Sized Trait:理解Sized Trait与动态大小类型
导言 Rust是一门以安全性和性能著称的系统级编程语言。在Rust中,类型大小的确定在编译期是非常重要的。然而,有些类型的大小在编译期是无法确定的,这就涉及到了Rust中的动态大小类型(DST)。为了保证在编译期可以确定类…...
前端框架学习-Vue(三)
目录 初识VueVue模板语法数据绑定el和data的两种写法事件的基本使用$emit在子组件中定义方法,执行父组件的方法 Vue中的事件修饰符:键盘事件计算属性监视属性条件渲染列表渲染表单数据收集过滤器 笔记内容来自:尚硅谷Vue2.0Vue3.0全套教程丨v…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
高保真组件库:开关
一:制作关状态 拖入一个矩形作为关闭的底色:44 x 22,填充灰色CCCCCC,圆角23,边框宽度0,文本为”关“,右对齐,边距2,2,6,2,文本颜色白色FFFFFF。 拖拽一个椭圆,尺寸18 x 18,边框为0。3. 全选转为动态面板状态1命名为”关“。 二:制作开状态 复制关状态并命名为”开…...
MLP实战二:MLP 实现图像数字多分类
任务 实战(二):MLP 实现图像多分类 基于 mnist 数据集,建立 mlp 模型,实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入,可视化图形数字; 2、完成数据预处理:图像数据维度转换与…...
window 显示驱动开发-如何查询视频处理功能(三)
D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针,该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...
比较数据迁移后MySQL数据库和ClickHouse数据仓库中的表
设计一个MySQL数据库和Clickhouse数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
NineData数据库DevOps功能全面支持百度智能云向量数据库 VectorDB,助力企业 AI 应用高效落地
NineData 的数据库 DevOps 解决方案已完成对百度智能云向量数据库 VectorDB 的全链路适配,成为国内首批提供 VectorDB 原生操作能力的服务商。此次合作聚焦 AI 开发核心场景,通过标准化 SQL 工作台与细粒度权限管控两大能力,助力企业安全高效…...
docker容器互联
1.docker可以通过网路访问 2.docker允许映射容器内应用的服务端口到本地宿主主机 3.互联机制实现多个容器间通过容器名来快速访问 一 、端口映射实现容器访问 1.从外部访问容器应用 我们先把之前的删掉吧(如果不删的话,容器就提不起来,因…...
