一道典型的贪心
抽象一下,其实就是区间中,不相交区间可以组成一条链,求链的最少数量
Solution
证明其实很简单,你只要找到一个能用的丢进去就好了,因为不管丢到哪一个栅栏,最后都还是要算最后时间的,所以其实没有差别
#include<bits/stdc++.h> using namespace std; int num=1,n; struct node{int st,ed,ind,used;}a[50005]; bool cmp(node a,node b){return a.st<b.st;}//按照开始时间排序 bool cmp2(node a,node b){return a.ind<b.ind;}//按照编号排序 priority_queue<pair<int,int> > q;//优先队列 int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].st,&a[i].ed),a[i].ind=i;//记录序号 sort(a+1,a+n+1,cmp); a[1].used=1;q.push(make_pair(-a[1].ed,1));//初始化一个牛棚 for(int i=2;i<=n;i++){ int x=-q.top().first; int tmp=q.top().second; if(x<a[i].st){//能够放进去就放 q.pop(); q.push(make_pair(-a[i].ed,tmp)); a[i].used=tmp; } else{//不能放就再开一个 q.push(make_pair(-a[i].ed,++num)); a[i].used=num;//记录 } } sort(a+1,a+n+1,cmp2); printf("%d\n",num); for(int i=1;i<=n;i++) printf("%d\n",a[i].used);//输出 }