bzoj1651 / P2859 [USACO06FEB]摊位预订Stall Reservations

P2859 [USACO06FEB]摊位预订Stall Reservations

维护一个按右端点从小到大的优先队列

蓝后把数据按左端点从小到大排序，顺序枚举。

每次把比右端点比枚举线段左端点小的数据从优先队列中删掉。

在整个过程中队列的最大长度即为答案。

总之用优先队列模拟一下就ok了

对于luogu需要输出方案数的问题：

再开一个优先队列存未用的编号

每次有线段进队时取走最小的编号，出队时再还回来。

似乎暴力也行（大雾）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 int max(int a,int b){return a>b?a:b;}

 #define N 50005

 struct data{

     int l,r,id;

     void init(int x){scanf("%d%d",&l,&r);id=x;}

     bool operator < (const data &tmp) const{

         return r>tmp.r;

     }

 }a[N]; priority_queue <data> h;

 priority_queue <int,vector<int>,greater<int> > d;

 bool cmp(const data &A,const data &B){return A.l<B.l;}

 int n,mp[N],ans;

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;++i) a[i].init(i),d.push(i);

     sort(a+,a+n+,cmp);

     for(int i=;i<=n;++i){

         if(!h.empty()){

             for(data q=h.top();!h.empty();q=h.top()){

                 if(q.r>=a[i].l) break;

                 d.push(mp[q.id]);h.pop();

             }

         }h.push(a[i]);

         mp[a[i].id]=d.top(); d.pop();

         ans=max(ans,h.size());

     }printf("%d\n",ans);

     for(int i=;i<=n;++i) printf("%d\n",mp[i]);

     return ;

 }