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

【二分+滑动窗口优化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 题意&#xff1a; 思路&#xff1a; 首先&#xff0c;要让最大值最小&#xff0c;很显然要二分 那么就相当于有了一个极差的限制&#xff0c;看能不能分组&#xff0c;每组至少m个元素 那么就是考虑分段DP&#xff0c;直接n^2很容易写 但是n …...

4.netty源码分析

1.pipeline调用handler的源码 //pipeline得到双向链表的头,next到尾部, 2.心跳源码 主要分析IdleStateHandler3个定时任务内部类 //考虑了网络传输慢导致出站慢的情况 //超时重新发送,然后关闭 ReadTimeoutHandler(继承IdleStateHandler 直接关闭连接)和WriteTimeoutHandler(继…...

性能优化点

Arts and Sciences - Computer Science | myUSF 索引3层&#xff08;高度为3&#xff09;一般对于数据库地址千万级别的表 大于2000万的数据进行分库分表存储 JVM整体结构及内存模型 JVM调优&#xff1a;主要为减少FULL GC的执行次数或者减少FULL GC执行时间 Spring Boot程序…...

leetcode301. 删除无效的括号(java)

删除无效的括号 leetcode301. 删除无效的括号题目描述暴力搜索 剪枝代码演示 回溯算法 leetcode301. 删除无效的括号 难度 困难 https://leetcode.cn/problems/remove-invalid-parentheses/description/ 题目描述 给你一个由若干括号和字母组成的字符串 s &#xff0c;删除最小…...

快速制作美容行业预约小程序

随着科技的不断进步&#xff0c;移动互联网的快速发展&#xff0c;小程序成为了很多行业迅速发展的利器。对于美容行业来说&#xff0c;一款美容预约小程序不仅可以方便用户进行预约&#xff0c;还可以提升美容店铺的服务质量和管理效率。下面&#xff0c;我们来介绍一下如何快…...

Golang之路---03 面向对象——结构体

结构体 结构体定义 在之前学过的数据类型中&#xff0c;数组与切片&#xff0c;只能存储同一类型的变量。若要存储多个类型的变量&#xff0c;就需要用到结构体&#xff0c;它是将多个任意类型的变量组合在一起的聚合数据类型。 每个变量都成为该结构体的成员变量。   可以理…...

【网络编程】poll

主旨思想 用一个结构体记录文件描述符集合&#xff0c;并记录用户态状态和内核态状态 函数说明 概览 #include <poll.h> struct pollfd { int fd; /* 委托内核检测的文件描述符 */ short events; /* 委托内核检测文件描述符的什么事件 */ short revents; /* 文件描述…...

配置VS Code 使其支持vue项目断点调试

起因 每个应用&#xff0c;不论大小&#xff0c;都需要理解程序是如何运行失败的。当我们写的程序没有按照自己写的逻辑走的时候&#xff0c;我们就会逐步一一排查问题。在平常开发过程中我们可能会借助 console.log 来排查,但是现在我们可以借助 VS Code 断点来调试项目。 前…...

第一百零一回 如何在组件树之间共享数据

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了"如何实现文件存储"相关的内容&#xff0c;本章回中将介绍 如何实现组件之间共享数据。闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 数据共享是程序中常用的功能&#xff0c;本章回介绍如何…...

Golang进阶学习

Golang进阶学习 视频地址&#xff1a;https://www.bilibili.com/video/BV1Pg41187AS?p35 1、包 1.1、包的引入 使用包的原因&#xff1a; 我们不可能把所有函数放在同一个源文件中&#xff0c;可以分门别类的放在不同的文件中 解决同名问题&#xff0c;同一个文件中不可以…...

【Linux】常用的基本指令

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前正在学习c和算法 ✈️专栏&#xff1a;Linux &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章有啥瑕疵&#xff0c;希望大佬指点一二 如果文章对…...

栈溢出几种情况及解决方案

一、局部数组过大。当函数内部的数组过大时&#xff0c;有可能导致堆栈溢出。 二、递归调用层次太多。递归函数在运行时会执行压栈操作&#xff0c;当压栈次数太多时&#xff0c;也会导致堆栈溢出。 三、指针或数组越界。这种情况最常见&#xff0c;例如进行字符串拷贝&#…...

go 内存分配

关注 go 语言内存分配策略&#xff0c;主要是想了解 go 的性能。申请不同大小的内存&#xff0c;性能开销是有差别的&#xff0c;申请内存越大&#xff0c;耗时也越久&#xff0c;性能也越差。 内存分配 参考 Go1.17.13 版本源码&#xff0c;从内存分配大小上区分了 tiny、sm…...

Maven pom.xml文件中build,plugin标签的具体使用

<build> 标签 <build> 标签是 pom.xml 文件中一个重要的标签&#xff0c;用于配置 Maven 项目的构建过程。在 <build> 标签下&#xff0c;可以配置构建相关的设置&#xff0c;包括源代码目录、输出目录、插件配置等。 以下是 <build> 标签的详细使用方…...

批量插入数据、MVC三层分离

八、批量插入数据 1、使用Statement&#xff08;&#xff09; 2、使用PreparedStatement() 3、使用批量操作API 4、优化 九、MVC三层分离...

【IMX6ULL驱动开发学习】21.Linux驱动之PWM子系统(以SG90舵机为例)

1.设备树部分 首先在 imx6ull.dtsi 文件中已经帮我们定义好了一些pwm的设备树节点&#xff0c;这里以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绑定的值是无法检测到用户自己输入的。 解决思路&#xff1a; el-cascader 没有提供…...

大数据技术之Clickhouse---入门篇---SQL操作、副本

星光下的赶路人star的个人主页 积一勺以成江河&#xff0c;累微尘以崇峻极 文章目录 1、SQL操作1.1 Insert1.2 Update 和 Delete1.3 查询操作1.4 alter操作1.5 导出数据 2、副本2.1 副本写入流程2.2 配置步骤 1、SQL操作 基本上来说传统关系型数据库&#xff08;以 MySQL 为例…...

【Rust 基础篇】Rust Sized Trait:理解Sized Trait与动态大小类型

导言 Rust是一门以安全性和性能著称的系统级编程语言。在Rust中&#xff0c;类型大小的确定在编译期是非常重要的。然而&#xff0c;有些类型的大小在编译期是无法确定的&#xff0c;这就涉及到了Rust中的动态大小类型&#xff08;DST&#xff09;。为了保证在编译期可以确定类…...

前端框架学习-Vue(三)

目录 初识VueVue模板语法数据绑定el和data的两种写法事件的基本使用$emit在子组件中定义方法&#xff0c;执行父组件的方法 Vue中的事件修饰符&#xff1a;键盘事件计算属性监视属性条件渲染列表渲染表单数据收集过滤器 笔记内容来自&#xff1a;尚硅谷Vue2.0Vue3.0全套教程丨v…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

2.2.2 ASPICE的需求分析

ASPICE的需求分析是汽车软件开发过程中至关重要的一环&#xff0c;它涉及到对需求进行详细分析、验证和确认&#xff0c;以确保软件产品能够满足客户和用户的需求。在ASPICE中&#xff0c;需求分析的关键步骤包括&#xff1a; 需求细化&#xff1a;将从需求收集阶段获得的高层需…...