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

【每日一题】补档 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 1n,len105
  • 0 ≤ s ≤ 1 0 9 0\leq s\leq 10^9 0s109
  • − 1 0 9 ≤ a i ≤ 1 0 9 -10^9\leq a_i\leq 10^9 109ai109

题解

状态定义
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.ij+1len

暴力做法

直接枚举所有的 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] [j1,ilen] 中的 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] [l1,rlen] 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 的数组&#xff0c;将这个数组进行拆分成若干个连续子数组&#xff0c; 使得每个子数组的最大值减去最小值小于等于 s s s &#xff0c; 且每个子数组的长度大于等于 l e n len len 。 问最少可以拆分成多少个连续子数组&#xff0…...

向量数据库和普通关系型数据库的区别,LAXCUS支持哪种数据库?

这是一位Laxcus用户在后台的提问&#xff0c;贴出来供大家参考&#xff1a; 1. 向量数据库与传统的关系型数据库主要有以下几个区别&#xff1a; 数据类型&#xff1a;向量数据库专门用于存储和查询向量数据&#xff0c;而传统数据库可以存储各种类型的数据&#xff0c;如文本…...

操作系统 --- 存储器管理

一、简答题 1.存储器管理的基本任务&#xff0c;是为多道程序的并发执行提供良好的存储器环境。请问好的存储器环境”应包含哪几个方面&#xff1f; 答&#xff1a; 2.内存保护是否可以完全由软件实现&#xff1f;为什么&#xff1f; 答&#xff1a;内存保护的主要任务是确保每…...

Python selenium无界面headless

视频版教程&#xff1a;一天掌握python爬虫【基础篇】 涵盖 requests、beautifulsoup、selenium Chrome-headless 模式&#xff0c; Google 针对 Chrome 浏览器 59版 新增加的一种模式&#xff0c;可以让你不打开UI界面的情况下使用 Chrome 浏览器&#xff0c;所以运行效果与 …...

JavaScript 中的负无穷大是什么?

在 JavaScript 中&#xff0c;负无穷大表示为 -Infinity。它是一个特殊的数值&#xff0c;用于表示比任何实数都要小的值。 负无穷大用于表示超出数值范围的情况&#xff0c;例如在进行数学计算时发生了溢出或出现了无法表示的结果。它可以通过将负无穷大赋值给变量或通过某些…...

2023年十大地推和网推拉新app推广接单平台,一手单渠道

做地推最重要的一定是找好项目&#xff0c;找好项目最关键的一定是地推app接任务平台&#xff0c;所以这十大靠谱的地推拉新接单平台&#xff0c;都是我们精心筛选的&#xff0c;2023年从事地推和网推拉新作业。 1&#xff1a;聚量推客 “聚量推客”汇聚了众多市场上有的和没有…...

mybatis-plus的进阶使用

文章目录 自定义xml的sql脚本配置mybaits的全局配置文件mybatis-plus优化&#xff0c;指定select数据库乐观锁mybatis-plus实现数据库乐观锁mybatis-plus实现逻辑删除 自定义xml的sql脚本 这里的使用和mybatis一样 编写mapper.xml文件 <?xml version"1.0" enc…...

centos安装vim编辑器

第一步检查centos的vim编辑器包是否完整 rpm -qa|grep vim //查看Vim编辑器需要安装的四个包是否完整 第二步&#xff1a;一般安装vim编辑器需要一下四个安装包&#xff0c;缺失了之后可对应下载 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元一个月&#xff0c;一年288元&#xff0c;以前是30M峰值带宽&#xff0c;现在是20M峰值带宽&#xff0c;阿腾云atengyun.com分享腾讯云香港轻量应用服务器性能测评&#xff0c;包括香港轻量服务器配置价格表、CPU性能和CN2网络延迟测试&am…...

深度学习之基于YoloV8的行人跌倒目标检测系统

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

Seata入门系列【16】XA模式入门案例

1 前言 在之前&#xff0c;我们试过了AT、TCC 模式&#xff0c;Seata 还支持XA 模式。 2 XA 协议 XA协议由Tuxedo首先提出的&#xff0c;并交给X/Open组织&#xff0c;作为资源管理器&#xff08;数据库&#xff09;与事务管理器的接口标准。Oracle、Informix、DB2和Sybase等…...

高级深入--day44

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

Apache Doris (四十八): Doris表结构变更-替换表

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

消息认证码--数字签名--证书

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

四个制作PPT的小技巧

制作PPT已经很麻烦了&#xff0c;学习一些小技巧可以帮助我们省时省力吧&#xff01; 技巧一&#xff1a;自动更新日期和时间 当我们给幻灯片添加了页脚并且是时间日期&#xff0c;可以通过设置达到自动更新&#xff0c;这样我们就不需要每次修改的时候都要手动更新日期和时间…...

Echarts饼状图grid设置

饼状图不能设置grid&#xff0c;而是center {type: "pie",radius: ["30%", "70%"],center: ["50%", "25%"], }center 圆心&#xff1a;控制圆的位置 radius 饼图的半径 控制显示尺寸 参考文章 Echarts饼状图设置...

系列三、Spring IOC

一、概述 IOC的中文意思是控制反转&#xff0c;通俗地讲就是把创建对象的控制权交给了Spring去管理&#xff0c;以前是由程序员自己去创建控制对象&#xff0c;现在交由Spring去创建控制。 二、优点 集中管理对象&#xff0c;方便维护&#xff0c;降低耦合度。 三、IOC的底层…...

electron汇总

python3自带了pip pip search已经被禁用&#xff0c;安装pip—— pip install pip-searchpython3.x移除了distutils 管理员权限下运行cmd&#xff0c;运行以下命令 // 修改pip镜像地址 pip config set global.index-url https://mirrors.aliyun.com/pypi/simple/ // 安装 Set…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...