买菜 - 题目列表

形式化题目

给定两组互不重叠且按时间递增排列的闭区间 $\{[a_i, b_i]\}_{i=1}^n$ 与 $\{[c_i, d_i]\}_{i=1}^n$ ，区间 $[s, t]$ 的长度为 $t - s$ 。求两组区间交叠部分的总长度，即

\sum_{1\le i,j\le n} \max(0,\ \min(b_i, d_j) - \max(a_i, c_j)).

思路

朴素做法

小数据可以枚举第一人的每一段与第二人的每一段，两段相交时累加交集长度 $\max(0,\min(r_1,r_2)-\max(l_1,l_2))$ 。这一做法时间复杂度 $O(n^2)$ ，作为对拍基准。

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
// brute.cpp：小数据暴力解，枚举两人的每一对装车区间，累加交集长度。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

int n;
int left_h[MAXN], right_h[MAXN];   // 小 H 的装车时间段
int left_w[MAXN], right_w[MAXN];   // 小 W 的装车时间段

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> left_h[i] >> right_h[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> left_w[i] >> right_w[i];
    }

    // 枚举所有区间对，交集长度取 max(0, min(r1,r2) - max(l1,l2))。
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int overlap_left = max(left_h[i], left_w[j]);
            int overlap_right = min(right_h[i], right_w[j]);
            if (overlap_left < overlap_right) {
                answer += overlap_right - overlap_left;
            }
        }
    }
    cout << answer << '\n';

    return 0;
}

双指针线性推进

因为两组区间内部都有序且互不重叠，只需维护当前的小 H 段 $i$ 与小 W 段 $j$ 。

先累加这两段的交集长度。
结束时刻更早的区间不可能再和对方后续任何区间相交，因此推进它的指针。

当结束时刻相等时，推进任意一方都正确，代码约定推进第二个指针。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

int n;
int left_h[MAXN], right_h[MAXN];   // 小 H 的装车时间段 [left_h[i], right_h[i]]
int left_w[MAXN], right_w[MAXN];   // 小 W 的装车时间段 [left_w[i], right_w[i]]

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> left_h[i] >> right_h[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> left_w[i] >> right_w[i];
    }

    // 两段区间 [l1,r1] 与 [l2,r2] 的交集长度为 max(l1,l2)..min(r1,r2) 的长度。
    int answer = 0;
    int i = 1, j = 1;
    while (i <= n && j <= n) {
        int overlap_left = max(left_h[i], left_w[j]);
        int overlap_right = min(right_h[i], right_w[j]);
        if (overlap_left < overlap_right) {
            answer += overlap_right - overlap_left;
        }

        // 结束时刻更早的一方不可能再和对方的后续区间相交，推进它。
        if (right_h[i] < right_w[j]) {
            i++;
        } else {
            j++;
        }
    }
    cout << answer << '\n';

    return 0;
}

复杂度

时间：两个指针各至多前进 $n$ 次， $O(n)$ 。
空间：保存两组区间， $O(n)$ 。

总结

处理两组有序、不重叠的区间时，不必枚举所有区间对。当前两段比较后，结束更早的一段已没有后续机会，这正是双指针能线性推进的原因。

买菜

目录

形式化题目

思路

朴素做法

双指针线性推进

代码

复杂度

总结