白城市住房建设局网站,网站自己做还是找人做,兴义市住房和城乡建设局网签网站,网站建立的公司题目内容 原题链接 给定一个长度为 n n n 的数组#xff0c;将这个数组进行拆分成若干个连续子数组#xff0c; 使得每个子数组的最大值减去最小值小于等于 s s s #xff0c; 且每个子数组的长度大于等于 l e n len len 。
问最少可以拆分成多少个连续子数组#xff0…题目内容 原题链接 给定一个长度为 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[j1,\cdots,i]\}-\min\{a[j1,\cdots,i]\}\leq s 1.max{a[j1,⋯,i]}−min{a[j1,⋯,i]}≤s 2. i − j 1 ≥ l e n 2. i-j1\geq len 2.i−j1≥len
暴力做法
直接枚举所有的 j j j
时间复杂度 O ( n 2 ) O(n^2) O(n2)
优化做法1
考虑如何加速找到所有合法的 j j j 当 j j j 越小即 [ j 1 , i ] [j1,i] [j1,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 pairint, 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_queuePII, vectorPII, greaterPII 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;
}
