Studying Father's luogu blog

Studying Father's luogu blog

从零至灵,由壹达意

题解 P3661 【[USACO17FEB]Why Did the Cow Cross the Road I S】

posted on 2019-08-19 17:13:34 | under 题解 |

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

我们将 $ 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;
}