【YbtOJ高效进阶贪心3】畜栏预定

链接

YbtOJ高效进阶 贪心-3

题目描述

有N头牛在畜栏中吃草。每个畜栏在同一时间段只能提供给一头牛吃草&＃xff0c;所以可能会需要多个畜栏&＃xff0c;给出第i头牛开始吃草的时间区间[ai,bi][a_i, b_i][ai​,bi​] &＃xff0c;求需要的最少畜栏数和每头牛对应的畜栏方案。

样例输入

5
1 10
2 4
3 6
5 8
4 7


样例输出

4
1
2
3
2
4


思路

对每头牛的开始时间从小到大排序
然后贪心&＃xff1f;
对于第i个牛&＃xff0c;它要么是进新的畜栏&＃xff0c;要么是进已经没牛的畜栏
1.进新的畜栏&＃xff0c;那只有每个畜栏都有牛&＃xff0c;才会开新的畜栏给这头牛
2.进没牛的畜栏&＃xff0c;那就要对每个畜栏中的牛的区间用一个小根堆去维护&＃xff0c;然后判断即可

代码

#include
#include
#include
#include
#include
#includeusing namespace std;int n, ans[100005];
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;struct tt
{int l, r, num;
}a[100005];bool cmp(tt a, tt b)
{return a.l < b.l;
}int main()
{scanf("%d", &n);for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)scanf("%d%d", &a[i].l, &a[i].r), a[i].num &＃61; i;sort(a &＃43; 1, a &＃43; n &＃43; 1, cmp);Q.push(make_pair(a[1].r, 1));ans[a[1].num] &＃61; 1;for(int i &＃61; 2; i <&＃61; n; &＃43;&＃43;i){if(!Q.size() || Q.top().first >&＃61; a[i].l) {ans[a[i].num] &＃61; Q.size() &＃43; 1;Q.push(make_pair(a[i].r, Q.size() &＃43; 1));}//对应思路中的第一种情况else {ans[a[i].num] &＃61; Q.top().second; Q.pop();Q.push(make_pair(a[i].r, ans[a[i].num]));}//第二种情况} printf("%d\n", Q.size());for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)printf("%d\n", ans[i]);
}