有 $N$ 头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定 $N$ 头牛和每头牛开始吃草的时间 $A$ 以及结束吃草的时间 $B$，每头牛在 $[A,B]$ 这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
输入格式
第 $1$ 行：输入一个整数 $N$。
第 $2..N+1$ 行：第 $i+1$ 行输入第 $i$ 头牛的开始吃草时间 $A$ 以及结束吃草时间 $B$，数之间用空格隔开。
输出格式
第 $1$ 行：输出一个整数，代表所需最小畜栏数。
第 $2..N+1$ 行：第 $i+1$ 行输出第 $i$ 头牛被安排到的畜栏编号，编号是从 $1$ 开始的 连续 整数，只要方案合法即可。
数据范围
$1≤N≤50000$,
$1≤A,B≤1000000$
输入样例：
输出样例：
题目解析
读完题，会有两个问题
- 如何知道每头牛什么时候安排畜栏吃草？
- 如何维护当前时间段已经空出来的畜栏？
第一个问题
我们只需要将每头牛按照开始吃草的时间从小到大进行排序，就可以知道此时应该给哪头牛安排畜栏，但是主要要记录每头牛之前的位置，因为输出要按照输入的顺序进行输出。
第二个问题（此题难点）
在满足每头牛按照开始吃草的时间从小到大的顺序前提下，满足每头牛的结束吃草的时间从小到大，然后我们再用一个小根堆维护每头牛结束吃草的时间，这样就可以知道在当前时间点是否有畜栏空出来，若有畜栏空出来，我们就不用新加一个畜栏。
思路容易，代码需要注意的地方很多
代码如下
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
| #include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
const int N = 50005;
struct root {
int A, B, ids;
} cow[N];
struct trees {
int ids, times = 0x3f;
} tree[N * 4];
int arrans[N];
int tnt = 0;
void up(int s) {
while(s > 1) {
if(tree[s / 2].times > tree[s].times) {
std::swap(tree[s / 2].times, tree[s].times);
std::swap(tree[s / 2].ids, tree[s].ids);
s /= 2;
} else break;
} return ;
}
void down(int s) {
int t = s + 1;
while(t <= tnt) {
if(t < tnt && tree[t].times > tree[t + 1].times) t++;
if(tree[s].times > tree[t].times) {
std::swap(tree[s].times, tree[t].times);
std::swap(tree[s].ids, tree[t].ids);
s = t;
t = s * 2;
} else break;
} return ;
}
int GetTopt() { return tree[1].times; }
int GetTopi() { return tree[1].ids; }
void Extract() {
tree[1].times = tree[tnt].times;
int x = tree[1].ids;
tree[1].ids = tree[tnt].ids;
tree[tnt].ids = x;
tnt--;
down(1);
}
void Insert(int x) {
tree[++tnt].times = x;
if(tree[tnt].ids == 0) tree[tnt].ids = tnt;
up(tnt);
}
bool cmp(root x, root y) {
if(x.A == y.A) return x.B < y.B;
else return x.A < y.A;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &cow[i].A, &cow[i].B);
cow[i].ids = i;
}
std::sort(cow + 1, cow + 1 + n, cmp);
int ans = 0;
for (int i = 1; i <= n; i++) {
if(i == 1) { Insert(cow[i].B); arrans[cow[i].ids] = 1; ans++; }
else {
if(cow[i].A > GetTopt()) {
arrans[cow[i].ids] = GetTopi();
Extract();
Insert(cow[i].B);
} else { ans++; arrans[cow[i].ids] = tnt + 1; Insert(cow[i].B); }
}
}
printf("%d\n", ans);
for (int i = 1; i <= n; i++) printf("%d\n", arrans[i]);
return 0;
}
|