【每日一题】补档 CF487B. Strip | 数据结构杂烩 -> 单调队列 | 困难

2023-10-28 20:04

本文主要是介绍【每日一题】补档 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 | 数据结构杂烩 -> 单调队列 | 困难的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/295626

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点