题目链接 & 题面
貌似是 USACO 原创，但我实在找不到原创的链接，只能在洛谷、 AcWing 和 POJ 上找了
洛谷：https://www.luogu.com.cn/problem/P2859
AcWing：https://www.acwing.com/problem/content/113/
题目描述
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
输入格式
第1行：输入一个整数N。
第2…N+1行：第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B，数之间用空格隔开。
输出格式
第1行：输入一个整数，代表所需最小畜栏数。
第2…N+1行：第i+1行输入第i头牛被安排到的畜栏编号，编号是从1开始的 连续 整数，只要方案合法即可。
（洛谷上题目描述是挤奶，AcWing上是吃草。。。）
基本算法
贪心
应该是比较显而易见的一个贪心，我刚开始都不觉得自己有多贪。。
按开始的时间把牛排序，然后依次放入畜栏，每次尽量放在已经使用过的畜栏中，如果没有就新建一个畜栏，cnt++。
由于可以放进任意一个畜栏，可以直接选出结束时间最早的畜栏比较，如果比当前时间早就可以放入，如果比当前时间晚就新建。
因此，可以通过 std::priority_queue 来维护一个小根堆来存放畜栏使用情况（当然手写也可以
priority_queue
我一般管这个叫优先队列，它可以保证队头的元素是 最小/最大 的。
对于这道题，存放畜栏的优先队列需要存放 畜栏中牛结束的时间 和 畜栏的编号，其中需要将最小值放在队首的是结束时间。因此，可以使用 std::pair 来作为一个单位存放。对于 pair ，每个元素进行比较时，先比较 first ，所以可以把结束时间放在 first 中。
当然，手写一个node然后重载运算符来自定义比较也可以，但这就是 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
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
using std::priority_queue;
using std::vector;
using std::sort;
using std::greater;
typedef std::pair<int,int> pint;
const int MAX=50005;
int n, cnt, le, ans[MAX];
priority_queue < pint, vector<pint>, greater<pint> > cl;
pint tmp;
struct Cow{
int start, end, nu;
}cow[MAX];
bool cmp(Cow x, Cow y) { return x.start < y.start; }
int main(){
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d %d", &cow[i].start, &cow[i].end);
cow[i].nu=i;
}
sort(cow, cow+n, cmp);
for(int i=0; i<n; i++){
if(!cl.empty() && cl.top().first<cow[i].start){
ans[cow[i].nu]=cl.top().second;
cl.pop();
tmp.first=cow[i].end;
tmp.second=ans[cow[i].nu];
cl.push(tmp);
}
else{
cnt++;
tmp.first=cow[i].end; tmp.second=cnt;
cl.push(tmp);
ans[cow[i].nu]=cnt;
}
}
printf("%d\n", cnt);
for(int i=0; i<n; i++) printf("%d\n", ans[i]);
return 0;
}
|