题目传送门
【题目大意】
【思路分析】
明显的贪心，按照开始吃草的时间从小到大排序，然后对于第$i$头牛，假设现在已经有$j$个畜栏，$r[j]$表示第$j$个畜栏里吃草的牛的结束时间，扫描$r$数组，判断第$i$头牛是否可以进入已经有的畜栏吃草，如果有就直接更新$r$的值，然后判断第$i+1$头牛，否则就加一个畜栏。
还有一种方法是用小根堆维护每个畜栏最后一头牛结束吃草的时间，尝试把当前的牛安排在堆顶(结束时间最早)的畜栏里。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #define rg register 6 #define go(i,a,b) for(rg int i=a;i<=b;i++) 7 using namespace std; 8 const int N=50002; 9 int n,to[N],r[N]; 10 struct line{ 11 int a,b,id,s; 12 }l[N]; 13 bool cmp(line A,line B){ 14 if(A.a!=B.a) return A.a<B.a; 15 else return A.b<B.b; 16 } 17 int main(){ 18 scanf("%d",&n); 19 go(i,1,n){ 20 scanf("%d%d",&l[i].a,&l[i].b); 21 l[i].id=i; 22 } 23 sort(l+1,l+1+n,cmp); 24 int num=1;l[1].s=1;r[1]=l[1].b; 25 go(i,1,n){ 26 to[l[i].id]=i; 27 if(i==1) continue; 28 go(j,1,num) 29 if(l[i].a>r[j]){ 30 r[j]=l[i].b;l[i].s=j; 31 break; 32 } 33 if(l[i].s==0) l[i].s=++num,r[num]=l[i].b; 34 } 35 printf("%d\n",num); 36 go(i,1,n) printf("%d\n",l[to[i]].s); 37 return 0; 38 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11250630.html
