Skip to content

「NOI2016」区间

题解约 1.4 千字
# 洛谷 # LibreOJ # 数据结构 # 线段树 # 2016 # NOI # 双指针
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

在数轴上有 nn 个闭区间 [l1,r1],[l2,r2],…,[ln,rn][l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]。现在要从中选出 mm 个区间，使得这 mm 个区间共同包含至少一个位置。换句话说，就是使得存在一个 xx，使得对于每一个被选中的区间 [li,ri][l_i, r_i]，都有 li≤x≤ril_i \leq x \leq r_i。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri][l_i, r_i] 的长度定义为 ri−lir_i − l_i，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1−1。

#输入格式

第一行包含两个正整数 n,mn, m 用空格隔开，意义如上文所述。保证 1≤m≤n1 \leq m \leq n。

接下来 nn 行，每行表示一个区间，包含用空格隔开的两个整数 lil_i 和 rir_i 为该区间的左右端点。

#输出格式

只有一行，包含一个正整数，即最小花费。

#输入输出样例

样例输入 #1

6 3
3 5
1 2
3 4
2 2
1 5
1 4

样例输出 #1

2

样例解释 #1

如图，当 n=6,m=3n = 6, m = 3 时，花费最小的方案是选取 [3,5][3, 5]、[3,4][3, 4]、[1,4][1, 4] 这三个区间，他们共同包含了 44 这个位置，所以是合法的。其中最长的区间是 [1,4][1, 4]，最短的区间是 [3,4][3, 4]，所以它的花费是 (4−1)−(4−3)=2(4 − 1) − (4 − 3) = 2。

#数据范围与提示

本题共 20 个测试点，各测试点信息见下表。

测试点编号 nn mm li,ril_i, r_i
1 2020 99 0≤li≤ri≤1000 \le l_i \le r_i \le 100
2 1010
3 199199 33 0≤li≤ri≤1000000 \le l_i \le r_i \le 100000
4 200200
5 10001000 22
6 20002000
7 199199 6060 0≤li≤ri≤50000 \le l_i \le r_i \le 5000
8 200200 5050
9 0≤li≤ri≤1090 \le l_i \le r_i \le 10^9
10 19991999 500500 0≤li≤ri≤50000 \le l_i \le r_i \le 5000
11 20002000 400400
12 500500 0≤li≤ri≤1090 \le l_i \le r_i \le 10^9
13 3000030000 20002000 0≤li≤ri≤1000000 \le l_i \le r_i \le 100000
14 4000040000 10001000
15 5000050000 1500015000
16 100000100000 2000020000
17 200000200000 0≤li≤ri≤1090 \le l_i \le r_i \le 10^9
18 300000300000 5000050000
19 400000400000 9000090000
20 500000500000 200000200000

对于 100%100\% 的测试数据，保证 1≤m≤n1 \leq m \leq n，1≤n≤5×1051 \leq n \leq 5 \times 10^5，1≤m≤2×1051 \leq m \leq 2 \times 10^5，0≤li≤ri≤1090 \leq l_i \leq r_i \leq 10^9。

#思路

先将所有线段按照长度排序，然后依次将线段覆盖到数轴上。这个过程可以使用线段树维护，每覆盖一段区间就将区间内所有点的计数 +1+1。

如果在第 ii 次覆盖后某个点被覆盖了超过 mm 层，那么就可以更新答案了。然后将最早覆盖的线段从数轴上移除，直到数轴上不存在被覆盖的层数 ≥m\geq m 的点。

由于题目所求的是「所有合法方案中最小的花费」，所以不需要考虑选取线段的总数量。

最后，根据数据范围中的「0≤li≤ri≤1090 \leq l_i \leq r_i \leq 10^9」可知本题需要离散化。

#代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <algorithm>
#include <limits>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;

struct node {
    int l, r, m, d;

    node(int _l = 0, int _r = 0)
        : l(_l), r(_r), m(0), d(0) {}
} tr[N << 3];

void pushup(int u) {
    tr[u].m = std::max(tr[u << 1].m, tr[u << 1 | 1].m);
}

void pushdown(int u) {
    if (!tr[u].d) return;

    tr[u << 1].d += tr[u].d;
    tr[u << 1 | 1].d += tr[u].d;

    tr[u << 1].m += tr[u].d;
    tr[u << 1 | 1].m += tr[u].d;

    tr[u].d = 0;
}

void build(int u, int l, int r) {
    tr[u] = node(l, r);

    if (l == r) return;

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int v) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].d += v;
        tr[u].m += v;

        return;
    }

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, v);
    if (r > mid) modify(u << 1 | 1, l, r, v);

    pushup(u);
}

int n, m, ans = std::numeric_limits<int>::max();
std::pair<int, int> seg[N];
std::vector<int> nums;

int len(int p) {
    return nums[seg[p].second - 1] - nums[seg[p].first - 1];
}

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

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> seg[i].first >> seg[i].second;

        nums.emplace_back(seg[i].first);
        nums.emplace_back(seg[i].second);
    }

    std::sort(seg + 1, seg + 1 + n, [&](const std::pair<int, int> &a, const std::pair<int, int> &b) {
        return a.second - a.first < b.second - b.first;
    });

    std::sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

    for (int i = 1; i <= n; i++) {
        seg[i].first = std::lower_bound(nums.begin(), nums.end(), seg[i].first) - nums.begin() + 1;
        seg[i].second = std::lower_bound(nums.begin(), nums.end(), seg[i].second) - nums.begin() + 1;
    }

    build(1, 1, nums.size());

    for (int i = 1, l = 1; i <= n; i++) {
        modify(1, seg[i].first, seg[i].second, 1);

        while (tr[1].m >= m) {
            ans = std::min(ans, len(i) - len(l));
            modify(1, seg[l].first, seg[l].second, -1);
            l++;
        }
    }

    cout << (ans == std::numeric_limits<int>::max() ? -1 : ans) << endl;

    return 0;
}