[洛谷 3661][USACO17FEB]Why Did the Cow Cross the Road I S

题目链接

https://www.luogu.org/problem/P3661

题解

先考虑一个朴素的贪心做法。

我们将 \(T_i\) 排序，对于每个 \(T_i\)，将其与满足条件且右端点最靠左的区间进行匹配。

这样的复杂度是 \(O(nc)\) 的，听说有人过了，但这样的解法其实还有很大优化空间。

我们将区间按左端点为关键字排序，建立一个以右端点为关键字的小根堆。

对于每个 \(T_i\)，我们将所有左端点小于 \(T_i\) 的区间插入堆（这些区间都将成为候选的可安排区间），接着将所有右端点小于 \(T_i\) 的区间从堆中弹出（因为 \(T_i\) 递增，未来这些区间也不可能被安排）。

执行完上面几步后，堆顶的区间正满足上面朴素做法中的“满足条件且右端点最靠左的区间”，可以与当前 \(T_i\) 匹配。

该算法的复杂度是 \(O(n \log n)\)。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
struct seg
{
 int l,r;
 bool operator<(const seg&a)const
 {
  return r>a.r;
 }
}s[20005];
int a[20005],vis[20005];
priority_queue<seg> q;
bool cmp(const seg&a,const seg&b)
{
 return a.l<b.l;
}
int main()
{
 int c,n;
 scanf("%d%d",&c,&n);
 for(int i=1;i<=c;i++)
  scanf("%d",&a[i]);
 sort(a+1,a+c+1);
 for(int i=1;i<=n;i++)
  scanf("%d%d",&s[i].l,&s[i].r);
 sort(s+1,s+n+1,cmp);
 int cur=1,ans=0;
 for(int i=1;i<=c;i++)
 {
  while(cur<=n&&s[cur].l<=a[i])
   q.push(s[cur++]);
  while(!q.empty()&&q.top().r<a[i])
   q.pop();
  if(!q.empty())ans++,q.pop();
 }
 printf("%d\n",ans);
 return 0;
}