【每日一题】补档 CF487B. Strip | 数据结构杂烩 -> 单调队列 | 困难
题目内容
原题链接
给定一个长度为 n n n 的数组,将这个数组进行拆分成若干个连续子数组,
使得每个子数组的最大值减去最小值小于等于 s s s ,
且每个子数组的长度大于等于 l e n len len 。
问最少可以拆分成多少个连续子数组,如果不可以,则输出 − 1 -1 −1
数据范围
- 1 ≤ n , l e n ≤ 1 0 5 1\leq n,len\leq 10^5 1≤n,len≤105
- 0 ≤ s ≤ 1 0 9 0\leq s\leq 10^9 0≤s≤109
- − 1 0 9 ≤ a i ≤ 1 0 9 -10^9\leq a_i\leq 10^9 −109≤ai≤109
题解
状态定义
d p [ i ] dp[i] dp[i] 表示将前 i i i 个数可以拆分出的最少的连续子数组。
状态转移
d p [ i ] = min { d p [ j ] } + 1 dp[i]= \min\{dp[j]\}+1 dp[i]=min{dp[j]}+1
这里需要满足如下两个条件:
1. max { a [ j + 1 , ⋯ , i ] } − min { a [ j + 1 , ⋯ , i ] } ≤ s 1. \max\{a[j+1,\cdots,i]\}-\min\{a[j+1,\cdots,i]\}\leq s 1.max{a[j+1,⋯,i]}−min{a[j+1,⋯,i]}≤s
2. i − j + 1 ≥ l e n 2. i-j+1\geq len 2.i−j+1≥len
暴力做法
直接枚举所有的 j j j
时间复杂度: O ( n 2 ) O(n^2) O(n2)
优化做法1
考虑如何加速找到所有合法的 j j j
当 j j j 越小,即 [ j + 1 , i ] [j+1,i] [j+1,i] 这个区间的最大值越大,最小值越小,那么就极值之差就越有可能大于等于 s s s 。
那么这部分就是满足二段性的,如此就可以二分。
右端点为 i i i ,二分左端点 j j j ,那么 [ j , i ] [j, i] [j,i] 的区间极值之差如果大于 s s s ,那么左端点应该更大,否则应该继续二分尝试减小左端点。
如此二分的时候应该快速找到区间极值,这部分用 R M Q RMQ RMQ 来解决。
我们最终二分出的左端点为 j j j ,那么需要找到区间 [ j − 1 , i − l e n ] [j-1, i-len] [j−1,i−len] 中的 d p dp dp 最小值。这部分因为是动态区间求最值,线段树或者优先队列懒 pop 来解决。
时间复杂度: O ( n log n ) O(n\log n) O(nlogn)
优化做法2
考虑到这里很多都是求区间的极值,而且对于每个右端点,其左端点一定是单调不减的,所以可以考虑双指针。
枚举右端点 r r r,然后移动左端点 l l l,使得区间最大值减去最小值小于等于 s s s 。
q m a x qmax qmax 是一个单调递减的队列,队头存储的是区间最大值
q m i n qmin qmin 是一个单调递增的队列,队头存储的是区间最小值
如此就可以 O ( 1 ) O(1) O(1) 快速查出区间极值。
此外,我们还需要知道最终得到左端点 l l l ,区间 [ l − 1 , r − l e n ] [l-1,r-len] [l−1,r−len] 的 d p dp dp 最小值。这部分同样可以用一个单调递增的队列来维护。
时间复杂度: O ( n ) O(n) O(n)
优化做法1代码一
#include <bits/stdc++.h>
using namespace std;const int N = 100010;
const int INF = 0x3f3f3f3f;
const int BIT = 17;int qmax[BIT][N];
int qmin[BIT][N];
int lg[N];
int a[N];
int n, s, len;
int dp[N];void init_rmq() {for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= n; ++j) qmax[0][j] = qmin[0][j] = a[j];for (int k = 1; k < BIT; ++k)for (int j = 1; j + (1 << k) - 1 <= n; ++j) {qmax[k][j] = max(qmax[k - 1][j], qmax[k - 1][j + (1 << (k - 1))]);qmin[k][j] = min(qmin[k - 1][j], qmin[k - 1][j + (1 << (k - 1))]);}
}int query_seg(int left, int right) {int bit = lg[right - left + 1];return max(qmax[bit][left], qmax[bit][right - (1 << bit) + 1]) - min(qmin[bit][left], qmin[bit][right - (1 << bit) + 1]);
};struct Node {int l, r;int val;
}tr[N << 2];void build(int u, int l, int r) {tr[u] = {l, r, INF};if (l == r) return;int mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}int query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return tr[u].val;}int mid = (tr[u].l + tr[u].r) >> 1;int ans = INF;if (l <= mid) ans = min(ans, query(u << 1, l, r));if (r > mid) ans = min(ans, query(u << 1 | 1, l, r));return ans;
}void modify(int u, int p, int x) {if (tr[u].l == tr[u].r) {tr[u].val = x;return;}int mid = (tr[u].l + tr[u].r) >> 1;if (p <= mid) modify(u << 1, p, x);else modify(u << 1 | 1, p, x);tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}int main()
{scanf("%d%d%d", &n, &s, &len);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);init_rmq();build(1, 0, n);// 考虑每个点 i 向左的最大值和最小值// 二分最短的,然后我需要知道这个区间里的最大值减最小值// dp[i] 表示前 i 个点需要拆分成的最少段for (int i = 1; i <= n; ++i) dp[i] = INF;dp[0] = 0;modify(1, 0, 0);for (int i = len; i <= n; ++i) {if (query_seg(i - len + 1, i) > s) continue;int left = 1, right = i - len + 1;while (left < right) {int mid = (left + right) >> 1;if (query_seg(mid, i) > s) left = mid + 1;else right = mid;}// 查 left - 1 到 i - len 的最小值dp[i] = min(dp[i], query(1, left - 1, i - len) + 1);// 单点最小值更新if (dp[i] < INF) {modify(1, i, dp[i]);}}printf("%d\n", dp[n] == INF ? -1 : dp[n]);return 0;
}
优化做法1代码二
#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 100010;
const int INF = 0x3f3f3f3f;
const int BIT = 17;int qmax[BIT][N];
int qmin[BIT][N];
int lg[N];
int a[N];
int n, s, len;
int dp[N];void init_rmq() {for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= n; ++j) qmax[0][j] = qmin[0][j] = a[j];for (int k = 1; k < BIT; ++k)for (int j = 1; j + (1 << k) - 1 <= n; ++j) {qmax[k][j] = max(qmax[k - 1][j], qmax[k - 1][j + (1 << (k - 1))]);qmin[k][j] = min(qmin[k - 1][j], qmin[k - 1][j + (1 << (k - 1))]);}
}int query_seg(int left, int right) {int bit = lg[right - left + 1];return max(qmax[bit][left], qmax[bit][right - (1 << bit) + 1]) - min(qmin[bit][left], qmin[bit][right - (1 << bit) + 1]);
};int main()
{scanf("%d%d%d", &n, &s, &len);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);init_rmq();// 考虑每个点 i 向左的最大值和最小值// 二分最短的,然后我需要知道这个区间里的最大值减最小值// dp[i] 表示前 i 个点需要拆分成的最少段for (int i = 1; i <= n; ++i) dp[i] = INF;dp[0] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;for (int i = len; i <= n; ++i) {if (i == 5) {int x = 1;}if (dp[i - len] < INF) {heap.emplace(dp[i - len], i - len);}if (query_seg(i - len + 1, i) > s) continue;int left = 1, right = i - len + 1;while (left < right) {int mid = (left + right) >> 1;if (query_seg(mid, i) > s) left = mid + 1;else right = mid;}// 查 left - 1 到 i - len 的最小值while (!heap.empty() && heap.top().second < left - 1) {heap.pop();}if (!heap.empty()) {dp[i] = heap.top().first + 1;}}printf("%d\n", dp[n] == INF ? -1 : dp[n]);return 0;
}
优化做法2代码
#include <bits/stdc++.h>
using namespace std;const int N = 100010;
const int INF = 0x3f3f3f3f;
int n, s, len;
int a[N];
int dp[N];
struct Queue {int q[N]{};int hh, tt;Queue(): hh(0), tt(-1) {}void push(int x) { q[++tt] = x; }void pop_back() { --tt; }void pop_front() { ++hh; }bool empty() const { return hh > tt; }int front() const { return q[hh]; }int back() const { return q[tt]; }
}qmax, qmin, qdp;int main()
{scanf("%d%d%d", &n, &s, &len);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);memset(dp, 0x3f, (n + 1) * sizeof(int));dp[0] = 0;for (int r = 1, l = 1; r <= n; ++r) {// 找到这个区间里的最小值while (!qmin.empty() && a[qmin.back()] >= a[r]) qmin.pop_back();qmin.push(r);// 找到这个区间里的最大值while (!qmax.empty() && a[qmax.back()] <= a[r]) qmax.pop_back();qmax.push(r);// 此时区间 [l, r] 里的最小值和最大值都已确定// 我们需要使得挪动左端点,直到区间 max - min <= s// 挪动左端点就意味着 qmax 和 qmin 需要进行移动,使得 qmax 和 qmin 的值都是在 [l, r] 之间while (!qmin.empty() && !qmax.empty() && a[qmax.front()] - a[qmin.front()] > s) {l += 1;while (!qmin.empty() && qmin.front() < l) qmin.pop_front();while (!qmax.empty() && qmax.front() < l) qmax.pop_front();}if (r >= len && dp[r - len] < INF) {while (!qdp.empty() && dp[qdp.back()] >= dp[r - len]) qdp.pop_back();qdp.push(r - len);}while (!qdp.empty() && qdp.front() < l - 1) qdp.pop_front();if (r - l + 1 >= len && !qdp.empty()) {dp[r] = dp[qdp.front()] + 1;}}printf("%d\n", dp[n] == INF ? -1 : dp[n]);return 0;
}
相关文章:
【每日一题】补档 CF487B. Strip | 数据结构杂烩 -> 单调队列 | 困难
题目内容 原题链接 给定一个长度为 n n n 的数组,将这个数组进行拆分成若干个连续子数组, 使得每个子数组的最大值减去最小值小于等于 s s s , 且每个子数组的长度大于等于 l e n len len 。 问最少可以拆分成多少个连续子数组࿰…...
向量数据库和普通关系型数据库的区别,LAXCUS支持哪种数据库?
这是一位Laxcus用户在后台的提问,贴出来供大家参考: 1. 向量数据库与传统的关系型数据库主要有以下几个区别: 数据类型:向量数据库专门用于存储和查询向量数据,而传统数据库可以存储各种类型的数据,如文本…...

操作系统 --- 存储器管理
一、简答题 1.存储器管理的基本任务,是为多道程序的并发执行提供良好的存储器环境。请问好的存储器环境”应包含哪几个方面? 答: 2.内存保护是否可以完全由软件实现?为什么? 答:内存保护的主要任务是确保每…...
Python selenium无界面headless
视频版教程:一天掌握python爬虫【基础篇】 涵盖 requests、beautifulsoup、selenium Chrome-headless 模式, Google 针对 Chrome 浏览器 59版 新增加的一种模式,可以让你不打开UI界面的情况下使用 Chrome 浏览器,所以运行效果与 …...
JavaScript 中的负无穷大是什么?
在 JavaScript 中,负无穷大表示为 -Infinity。它是一个特殊的数值,用于表示比任何实数都要小的值。 负无穷大用于表示超出数值范围的情况,例如在进行数学计算时发生了溢出或出现了无法表示的结果。它可以通过将负无穷大赋值给变量或通过某些…...

2023年十大地推和网推拉新app推广接单平台,一手单渠道
做地推最重要的一定是找好项目,找好项目最关键的一定是地推app接任务平台,所以这十大靠谱的地推拉新接单平台,都是我们精心筛选的,2023年从事地推和网推拉新作业。 1:聚量推客 “聚量推客”汇聚了众多市场上有的和没有…...
mybatis-plus的进阶使用
文章目录 自定义xml的sql脚本配置mybaits的全局配置文件mybatis-plus优化,指定select数据库乐观锁mybatis-plus实现数据库乐观锁mybatis-plus实现逻辑删除 自定义xml的sql脚本 这里的使用和mybatis一样 编写mapper.xml文件 <?xml version"1.0" enc…...
centos安装vim编辑器
第一步检查centos的vim编辑器包是否完整 rpm -qa|grep vim //查看Vim编辑器需要安装的四个包是否完整 第二步:一般安装vim编辑器需要一下四个安装包,缺失了之后可对应下载 vim-minimal-7.4.160-2.el7.x86_64vim-common-7.4.160-4.el7.x86_64 v…...

PostgreSQL InvalidMessage Cache 同步机制
文章目录 背景InvalidMessages 基本类型InvalidMessages 数据结构概览共享内存 的 "ring-buffer" 结构Backend 本地的 InvalidMessages管理SharedInvalCatalogMsgSharedInvalCatcacheMsgSharedInvalRelcacheMsgSharedInvalSnapshotMsgSharedInvalSmgrMsgSharedInvalR…...

C#,数值计算——Globals的计算方法与源程序
1 文本格式 using System; using System.Text; namespace Legalsoft.Truffer { public static partial class Globals { //const int FLT_RADIX 2; //const int DBL_MANT_DIG 53; //const int INT_DIGITS 32; //const float FLT_…...

腾讯云香港服务器轻量24元一个月性能测试
腾讯云香港轻量应用服务器优惠价格24元一个月,一年288元,以前是30M峰值带宽,现在是20M峰值带宽,阿腾云atengyun.com分享腾讯云香港轻量应用服务器性能测评,包括香港轻量服务器配置价格表、CPU性能和CN2网络延迟测试&am…...

深度学习之基于YoloV8的行人跌倒目标检测系统
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、行人跌倒目标检测系统四. 总结 一项目简介 世界老龄化趋势日益严重,现代化的生活习惯又使得大多数老人独居,统计数据表…...

Seata入门系列【16】XA模式入门案例
1 前言 在之前,我们试过了AT、TCC 模式,Seata 还支持XA 模式。 2 XA 协议 XA协议由Tuxedo首先提出的,并交给X/Open组织,作为资源管理器(数据库)与事务管理器的接口标准。Oracle、Informix、DB2和Sybase等…...

高级深入--day44
Scrapy 和 scrapy-redis的区别 Scrapy 是一个通用的爬虫框架,但是不支持分布式,Scrapy-redis是为了更方便地实现Scrapy分布式爬取,而提供了一些以redis为基础的组件(仅有组件)。 pip install scrapy-redis Scrapy-redis提供了下面四种组件&a…...

Apache Doris (四十八): Doris表结构变更-替换表
🏡 个人主页:IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 🚩 私聊博主:加入大数据技术讨论群聊,获取更多大数据资料。 🔔 博主个人B栈地址:豹哥教你大数据的个人空间-豹哥教你大数据个人主页-哔哩哔哩视频 目录...

消息认证码--数字签名--证书
6. 消息认证码—>保证数据的完整性 "消息认证码 --- 消息被正确传送了吗?"6.1 什么是消息认证码 Alice 和 Bob 的故事 像以前一样,我们还是从一个Alice和Bob的故事开始讲起。不过,这一次Alice和Bob分别是两家银行,Alice银行通…...

四个制作PPT的小技巧
制作PPT已经很麻烦了,学习一些小技巧可以帮助我们省时省力吧! 技巧一:自动更新日期和时间 当我们给幻灯片添加了页脚并且是时间日期,可以通过设置达到自动更新,这样我们就不需要每次修改的时候都要手动更新日期和时间…...
Echarts饼状图grid设置
饼状图不能设置grid,而是center {type: "pie",radius: ["30%", "70%"],center: ["50%", "25%"], }center 圆心:控制圆的位置 radius 饼图的半径 控制显示尺寸 参考文章 Echarts饼状图设置...
系列三、Spring IOC
一、概述 IOC的中文意思是控制反转,通俗地讲就是把创建对象的控制权交给了Spring去管理,以前是由程序员自己去创建控制对象,现在交由Spring去创建控制。 二、优点 集中管理对象,方便维护,降低耦合度。 三、IOC的底层…...
electron汇总
python3自带了pip pip search已经被禁用,安装pip—— pip install pip-searchpython3.x移除了distutils 管理员权限下运行cmd,运行以下命令 // 修改pip镜像地址 pip config set global.index-url https://mirrors.aliyun.com/pypi/simple/ // 安装 Set…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...

Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...