Skip to content

「NOI2016」区间

检测到 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],都有 lixril_i \leq x \leq r_i

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

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

#输入格式

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

接下来 nn 行,每行表示一个区间,包含用空格隔开的两个整数 lil_irir_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],所以它的花费是 (41)(43)=2(4 − 1) − (4 − 3) = 2

#数据范围与提示

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

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

对于 100%100\% 的测试数据,保证 1mn1 \leq m \leq n1n5×1051 \leq n \leq 5 \times 10^51m2×1051 \leq m \leq 2 \times 10^50liri1090 \leq l_i \leq r_i \leq 10^9

#思路

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

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

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

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

#代码

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;
}