#P4311. 第4题-数据分析系统
-
1000ms
Tried: 6
Accepted: 1
Difficulty: 8
所属公司 :
拼多多
时间 :2025年10月26日
-
算法标签>动态规划
第4题-数据分析系统
解题思路
-
本题需要把数组划分成若干连续段,使每段满足:
- 段内最大值与最小值之差 ≤ A;
- 段长 ≥ B; 并使段数最少。
-
关键算法:
-
双指针 + 单调队列:用两个单调队列维护滑动窗口的最大值与最小值。右指针向右扩,若当前窗口不满足
max-min ≤ A,左指针右移并在队头弹出过期下标。这样可在 O(n) 得到对每个右端点i的“最左合法起点”L(i)(0-based)。 -
动态规划 + 区间最小值的单调队列:令
dp[i]为前i个元素(1-based)最少段数,dp[0]=0; 若选一段以i结尾,起点s需满足s ∈ [L(i-1), i-B](0−based对应的前缀切分点j=s,范围为[L(i-1), i-B])。 则dp[i] = 1 + minj∈[L(i−1),i−B]dp[j]
-
其中 j 的有效区间左右端点均随 i 单调移动,故可用另一条单调队列维护这段区间内 dp[j] 的滑动最小值,整体仍为 O(n)。
-
流程小结:
- 用两条单调队列维护
max/min,移动确定每个i的最左合法L; - 同步用一条单调队列维护区间
[L, i-B]上的dp最小值,得到dp[i]; - 答案为
dp[n],若不可达输出-1。
- 用两条单调队列维护
复杂度分析
- 时间复杂度:每个元素至多进出各队列一次,O(n)。
- 空间复杂度:
dp与若干队列,O(n)。
代码实现
Python
# 题意函数写在外部,主函数只做输入输出
# 使用双指针+单调队列维护区间max/min;再用单调队列维护dp的区间最小值
import sys
from collections import deque
INF = 10 ** 9
def min_segments(n, A, B, a):
# dp[i]: 前 i 个元素(1-based)的最少段数;dp[0]=0
dp = [INF] * (n + 1)
dp[0] = 0
# 维护窗口 [L..i-1] 的最大/最小值下标(0-based)
dq_max, dq_min = deque(), deque()
L = 0 # 当前窗口最左可行下标(0-based)
# 维护可选切分点 j 的滑动区间 [L, i-B] 上 dp[j] 的单调队列
cand = deque() # 存 j 下标,保持 dp[j] 递增
for i in range(1, n + 1):
idx = i - 1 # 新加入的元素下标(0-based)
# 插入最大值队列(保持从大到小)
while dq_max and a[dq_max[-1]] <= a[idx]:
dq_max.pop()
dq_max.append(idx)
# 插入最小值队列(保持从小到大)
while dq_min and a[dq_min[-1]] >= a[idx]:
dq_min.pop()
dq_min.append(idx)
# 收缩左端,直到满足 max - min <= A
while dq_max and dq_min and a[dq_max[0]] - a[dq_min[0]] > A:
L += 1
# 弹出过期下标
if dq_max and dq_max[0] < L:
dq_max.popleft()
if dq_min and dq_min[0] < L:
dq_min.popleft()
# 当前右端 i(1-based),可加入新的右边界切分点 j = i - B(0-based)
r = i - B
if r >= 0:
# cand 维持 dp[j] 的单调递增
while cand and dp[cand[-1]] >= dp[r]:
cand.pop()
cand.append(r)
# 合法区间的左边界为 L(0-based),即 j >= L
while cand and cand[0] < L:
cand.popleft()
if cand:
dp[i] = dp[cand[0]] + 1 # 选择区间内最优 j
return dp[n] if dp[n] < INF else -1
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
t = data[0]
p = 1
out = []
for _ in range(t):
n, A, B = data[p], data[p+1], data[p+2]
p += 3
a = data[p:p+n]
p += n
out.append(str(min_segments(n, A, B, a)))
print("\n".join(out))
if __name__ == "__main__":
main()
Java
// 类名必须为 Main,ACM 风格。使用双指针+单调队列与DP滑动最小值。
import java.io.*;
import java.util.*;
public class Main {
static final int INF = 1_000_000_000;
// 计算最少段数
static int minSegments(int n, long A, int B, long[] a) {
int[] dp = new int[n + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
Deque<Integer> dqMax = new ArrayDeque<>(); // 维护最大值下标
Deque<Integer> dqMin = new ArrayDeque<>(); // 维护最小值下标
int L = 0; // 当前窗口最左可行下标(0-based)
Deque<Integer> cand = new ArrayDeque<>(); // 维护区间 [L, i-B] 上 dp[j] 的单调队列
for (int i = 1; i <= n; i++) {
int idx = i - 1;
// 插入最大值队列(保持从大到小)
while (!dqMax.isEmpty() && a[dqMax.peekLast()] <= a[idx]) dqMax.pollLast();
dqMax.offerLast(idx);
// 插入最小值队列(保持从小到大)
while (!dqMin.isEmpty() && a[dqMin.peekLast()] >= a[idx]) dqMin.pollLast();
dqMin.offerLast(idx);
// 收缩左端,直到满足 max - min <= A
while (!dqMax.isEmpty() && !dqMin.isEmpty() && a[dqMax.peekFirst()] - a[dqMin.peekFirst()] > A) {
L++;
if (!dqMax.isEmpty() && dqMax.peekFirst() < L) dqMax.pollFirst();
if (!dqMin.isEmpty() && dqMin.peekFirst() < L) dqMin.pollFirst();
}
// 加入新的右边界切分点 j = i - B(0-based)
int r = i - B;
if (r >= 0) {
while (!cand.isEmpty() && dp[cand.peekLast()] >= dp[r]) cand.pollLast();
cand.offerLast(r);
}
// 弹出不在合法区间左边界之前的下标
while (!cand.isEmpty() && cand.peekFirst() < L) cand.pollFirst();
if (!cand.isEmpty()) {
dp[i] = dp[cand.peekFirst()] + 1;
}
}
return dp[n] >= INF ? -1 : dp[n];
}
// 简单高效读入
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, x = 0;
do { c = read(); } while (c <= 32);
if (c == '-') { sgn = -1; c = read(); }
while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
return x * sgn;
}
long nextLong() throws IOException {
int c, sgn = 1;
long x = 0;
do { c = read(); } while (c <= 32);
if (c == '-') { sgn = -1; c = read(); }
while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
return x * sgn;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int T = fs.nextInt();
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
int n = fs.nextInt();
long A = fs.nextLong();
int B = fs.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = fs.nextLong();
sb.append(minSegments(n, A, B, a)).append('\n');
}
System.out.print(sb.toString());
}
}
C++
// ACM 风格:主函数读入,功能函数在外部。
// 算法:双指针+单调队列维护区间 max/min;DP + 单调队列维护区间最小值。
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int minSegments(int n, long long A, int B, const vector<long long>& a) {
vector<int> dp(n + 1, INF);
dp[0] = 0;
deque<int> dqMax, dqMin; // 维护窗口内最大/最小值的下标
int L = 0; // 当前窗口最左可行下标(0-based)
deque<int> cand; // 维护 [L, i-B] 区间内 dp[j] 的单调队列(dp 值递增)
for (int i = 1; i <= n; i++) {
int idx = i - 1;
// 插入最大值队列(从大到小)
while (!dqMax.empty() && a[dqMax.back()] <= a[idx]) dqMax.pop_back();
dqMax.push_back(idx);
// 插入最小值队列(从小到大)
while (!dqMin.empty() && a[dqMin.back()] >= a[idx]) dqMin.pop_back();
dqMin.push_back(idx);
// 收缩左端直到满足 max - min <= A
while (!dqMax.empty() && !dqMin.empty() && a[dqMax.front()] - a[dqMin.front()] > A) {
L++;
if (!dqMax.empty() && dqMax.front() < L) dqMax.pop_front();
if (!dqMin.empty() && dqMin.front() < L) dqMin.pop_front();
}
// 右边界新增候选切分点 j = i - B(0-based)
int r = i - B;
if (r >= 0) {
while (!cand.empty() && dp[cand.back()] >= dp[r]) cand.pop_back();
cand.push_back(r);
}
// 弹出左侧越界的候选 j
while (!cand.empty() && cand.front() < L) cand.pop_front();
if (!cand.empty()) {
dp[i] = dp[cand.front()] + 1;
}
}
return dp[n] >= INF ? -1 : dp[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n, B;
long long A;
cin >> n >> A >> B;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
cout << minSegments(n, A, B, a) << "\n";
}
return 0;
}
题目内容
多多正在处理一批数据,需要把一条长度为 n ,从左到右依次排列的数组 a1,a2,…,an 裁剪成若干连续的数据段,用于录入公司的数据分析系统.
数据分析系统对于录入的数据块有两个要求
1.每段数据中的最大值与最小值之差需要 小于等于 A .
2.每段数据的长度需要 大于等于 B .
多多需要将该数组全部划分成若干连续的数据段,并且使得所有数据段都满足数据分析系统的要求.多多想知道,在满足上述条件的情况下,划分后的数据段的数量最少为多少,如果不能将数组全部划分,那么输出 −1 .
输入描述
第一行,包含一个正整数 T(1≤T≤3) 代表测试数据的组数
对于每组测试数据,分别有两行:
第一行,有三个正整数 n(1≤n≤105),A(0≤A≤109),B(1≤B≤105) .
第二行,包含 n 个整数,分别表示 a1,a2,...,an(−109≤ai≤109)
输出描述
对于每组数据,输出一个正整数,代表划分后最少的数据段的数量,如果不存在符合要求的划分,那么输出 -1.
样例1
输入
2
10 5 1
1 2 3 4 5 6 7 8 9 10
5 3 3
10 6 2 4 -1
输出
2
-1
说明
对于第一组数据,可以最少划分为两个数据段:
(1,2,3,4,5)(6,7,8,9,10)
对于第二组数据,无法找出符合要求的划分.