盛日辉的博客
0%

EOJ 5200. Bare Minimum Difference（尺取法+队列优化DP）

发表于 更新于 分类于

题目

题目链接：https://acm.ecnu.edu.cn/problem/5200/

思路

读完题只是隐约感觉可以用二分，但没有别的任何想法了。

于是问了 Gemini G 老师，它提示了可以用 尺取法 和 动态规划 来做。因为答案必定是由两个子数组的和相减得到的，而数据规模只有 $100$，因此可以枚举出所有的子数组和，然后排序之后利用尺取法即同向双指针来找到两个数作为划分之后所有区间的最大、最小的子数组和，判断这样的最大、最小子数组和能否被成功划分出来。

尺取法就像在序列上移动的一条“毛毛虫”或一个“伸缩滑窗”：它通过同向交替移动左、右两个端点，在 $O(n)$ 时间内高效地扫描出所有符合条件的区间。

简单来说，就是右端点负责扩张以寻找可行解，左端点负责收缩以寻找最优解。

如何判断呢？

G 老师给的方法是动态规划。定义 $dp[i]$ 表示数组的前 $i$ 个数字，是否能被合法地划分为若干个区间，使得每个区间的和 $S$ 都在范围 $[L, R]$ 之内。对于每一个位置 $i$ (从 $1$ 到 $n$)，尝试枚举上一个区间的结束位置 $j$：

但这样的时间复杂度达到了 $O(n^4)$（动态规划 $O(n^2)$，尺取法为 $O(M)$，$M$ 约为 $n^2$），不是太好。

因为我发现，数据都是正数，所以划分的子数组区间越大，子数组的和也就越大。假如我固定了区间的左端点：如果区间的和不到最小值，那就不断扩展右端点，使得区间和变大；当区间和落在 $[L,R]$ ，说明当前的区间 $[l, r]$ 是一个符合条件的区间；如果区间和比最大值还大，那就移动左端点缩小区间范围。

这可以通过维护一个队列来实现，队列中存可以作为左端点的下标。

一个小优化点是去重。因为子数组和会有重复。去重的方法可以直接去重，也可以在尺取法的过程中跳过重复的数（见 C++ 的代码），但这样有些麻烦和容易错。

具体实现和一些细节见代码。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from collections import deque

n = int(input())
nums = list(map(int, input().split()))
# 计算前缀和和所有子数组的和
pre_sum = [0]
all_sums = []
for i, x in enumerate(nums):
    s = 0
    for j in range(i, -1, -1):
        s += nums[j]
        all_sums.append(s)
    pre_sum.append(s)
# 去重
all_sums = sorted(list(set(all_sums)))


def check(L: int, R: int) -> bool:
    q = deque([0])  # 划分点
    for r in range(n):
        # 单个值都超了最大值，直接 return
        if nums[r] > R: return False
        while q:
            # 计算 [队头, r] 的子数组和
            s = pre_sum[r + 1] - pre_sum[q[0]]
            if s < L:  # 不到最小值，继续加入元素
                break
            elif L <= s <= R:
                if r == n - 1 and q[0] == 0:  # 排除只有一个区间的情况，保证至少划分出两个区间
                    q.popleft()
                    continue
                # [队头, r] 可以作为一个划分区间
                # 之后要考虑的是以 r+1 作为左端点的区间，所以将 r+1 入队
                q.append(r + 1)
                break
            else:  # 比最大值都大了，缩小区间的范围（出队）再看看
                q.popleft()
    # 如果队列不为空，变切最后一段也满足大于等于 L
    # 为什么再判断最后一段？
    # 因为上面的 if 里面如果最后一段比 最小值L 小就直接 break 了，但这是不符合条件的
    return q and L <= pre_sum[-1] - pre_sum[q[0]]  # <= R


left, right = 0, 0
ans = 0x3f3f3f3f
while right < len(all_sums):
    while left <= right and check(all_sums[left], all_sums[right]):
        # 找到可以满足条件的划分，更新答案
        ans = min(ans, all_sums[right] - all_sums[left])
        left += 1
    right += 1

print(ans)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 注释在 Python 代码里

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> nums(n);
    vector<int> pre_sum(n + 1);
    vector<int> all_sums;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        int s = 0;
        for (int j = i; j >= 0; j--) {
            s += nums[j];
            all_sums.push_back(s);
        }
        pre_sum[i + 1] = s;
    }
    sort(all_sums.begin(), all_sums.end());
    // all_sums.erase(unique(all_sums.begin(), all_sums.end()), all_sums.end());

    auto check = [&](int L, int R) -> bool {
        deque<int> q;
        q.push_back(0);
        for (int r = 0; r < n; r++) {
            while (!q.empty()) {
                int s = pre_sum[r + 1] - pre_sum[q.front()];
                if (s < L) break;
                else if (s > R) q.pop_front();
                else {
                    if (r == n - 1 && q.front() == 0) {
                        q.pop_front();
                        continue;
                    }
                    q.push_back(r + 1);
                    break;
                }
            }
        }
        return !q.empty() && L <= pre_sum.back() - pre_sum[q.front()] && pre_sum.back() - pre_sum[q.front()] <= R;
    };

    int ans = 0x3f3f3f3f;
    int left = 0, right = 0;
    while (right < all_sums.size()) {
        while (left <= right && check(all_sums[left], all_sums[right])) {
            ans = min(ans, all_sums[right] - all_sums[left++]);
            while (left && all_sums[left] == all_sums[left - 1]) left++;
        }
        right++;
        while (right && all_sums[right] == all_sums[right - 1]) right++;
    }
    cout << ans;
    return 0;
}