题目大意:
给你一个数字n与n头牛开始的挤奶时间与结束时间
现在有几个栏栅
栏栅可以放任意的牛但是里面不能有重叠的时间
问你需要几个栏栅
并输出每头牛所在的栏栅编号
(具体请看题目)
思路:贪心
想到的肯定是一头牛挤奶时间尽可能的早并且结束时间尽可能的早才能尽量的没有重叠时间
那么我们可以利用优先队列把结束时间早的牛放在前面
同时我们可以利用排序将开始时间早的牛放在前面
并且按顺序一个个放入优先队列中
因为结束时间早的要对应挤奶时间早的才能更好的放进一个栏栅里
这样就完成了操作
不过栏栅编号细节要注意一下,要再用一个变量存着
因为排序或优先队列都会打乱原本的编号顺序
(具体参照代码)
代码:
#include <iostream> #include <queue> #include <algorithm> using namespace std; struct node{ int st,en,pos; friend bool operator<(node a,node b){ return a.en>b.en;//在优先队列中按结束时间从小到大排序 } }; node a[50010]; int order[50010]; priority_queue<node>b; bool cmp(node a,node b){//按开始时间排序 if(a.st==b.st)return a.en<b.en; return a.st<b.st; } int main() { int t; cin>>t; for(int i=1;i<=t;i++){ cin>>a[i].st>>a[i].en; a[i].pos=i; } sort(a+1,a+1+t,cmp); b.push(a[1]); order[a[1].pos]=1; int ans=1; for(int i=2;i<=t;i++){ if(!b.empty()&&b.top().en<a[i].st){//正好结束时间小于开始时间,编入同一个栏栅 order[a[i].pos]=order[b.top().pos]; b.pop(); } else{ ans++; order[a[i].pos]=ans; } b.push(a[i]); } cout<<ans<<endl; for(int i=1;i<=t;i++){ cout<<order[i]<<endl; } return 0; }