POJ 3190 Stall Reservations （优先队列+结构体）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<map>
  7 #include<set>
  8 #include<vector>
  9 #include<queue>
 10 #include<list>
 11 #include<stack>
 12 //#include<unordered_map>
 13 using namespace std;
 14 #define ll long long 
 15 #define dd cout<<endl
 16 const int mod=1e9+7;
 17 const int nf=1e9+7;
 18 
 19 const int maxn=5e4+10;
 20 
 21 typedef struct
 22 {
 23     int a;
 24     int b;
 25     int number;
 26 } St;
 27 //优先队列+结构体，定义优先级 
 28 bool operator<(const St &x,const St &y)
 29 {
 30     return x.b > y.b;
 31  } 
 32  
 33 bool cmp(const St &x,const St &y)
 34 {
 35     if(x.a != y.a)
 36         return x.a < y.a;
 37     else
 38         return x.b < y.b;
 39 }
 40  
 41 St sum[maxn];
 42 
 43 int main()
 44 {
 45     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 46     
 47     int n;
 48     cin>>n;
 49     
 50     int a,b;
 51     
 52     priority_queue<St>q;    
 53     
 54     int ans=0;
 55     vector<St>v;
 56 
 57     for(int i=0;i<n;i++)
 58     {
 59         cin>>sum[i].a>>sum[i].b;
 60         sum[i].number=i;
 61     }
 62     
 63     sort(sum,sum+n,cmp);//这里先根据开始顺序排下序 
 64     
 65     for(int i=0;i<n;i++)
 66     {
 67         a=sum[i].a;//当前开始时间 
 68         b=sum[i].b;//当前结束时间 
 69         
 70         if(q.empty())//空的直接进篱笆 
 71         {
 72             ans++;
 73             q.push({ans,b});
 74             v.push_back({sum[i].number,ans});//记录 
 75         }
 76         else
 77         {
 78             St now=q.top();
 79             
 80             if(now.b < a)//当前开始时间大于最早的结束时间 
 81             {
 82                 q.pop();
 83                 
 84                 v.push_back({sum[i].number,now.a});//记录 
 85                 q.push({now.a,b});
 86             }
 87             else//在进一个篱笆 
 88             {
 89                 ans++;
 90                 q.push({ans,b});
 91                 v.push_back({sum[i].number,ans});//记录 
 92             }
 93         }    
 94     }
 95     
 96     cout<<ans<<endl;//篱笆数 
 97     
 98     sort(v.begin(),v.end(),cmp);//按奶牛序号排序 
 99     
100     for(int i=0;i<v.size();i++)//输出答案 
101         cout<<v[i].b<<endl;
102     
103     return 0;
104 }