BZOJ 1651 [Usaco2006 Feb]Stall Reservations 专用牛棚：优先队列【线段最大重叠层数】

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1651

题意：

　　给你n个线段[a,b]，问你这些线段重叠最多的地方有几层。

题解：

　　先将线段按左端点a升序排序。

　　开一个优先队列q（升序排序），里面存线段的右端点b。

　　枚举线段i，然后：

　　　　（1）将q中所有小于a[i]的元素弹出。

　　　　（2）插入b[i]。

　　　　（3）更新ans = max(ans,q.size())

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <queue>

 #define MAX_N 50005

 using namespace std;

 int n;

 int ans=;

 pair<int,int> p[MAX_N];

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

 int main()

 {

     cin>>n;

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

     {

         cin>>p[i].first>>p[i].second;

     }

     sort(p,p+n);

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

     {

         while(!q.empty() && q.top()<p[i].first) q.pop();

         q.push(p[i].second);

         ans=max(ans,(int)q.size());

     }

     cout<<ans<<endl;

 }

巴特西

BZOJ 1651 [Usaco2006 Feb]Stall Reservations 专用牛棚：优先队列【线段最大重叠层数】

最新文章

热门文章