题解 P3661 【[USACO17FEB]Why Did the Cow Cross the Road I S】
StudyingFather
2019-08-19 17:13:34
先考虑一个朴素的贪心做法。
我们将 $ T_i $ 排序，对于每个 $ T_i $，将其与满足条件且右端点最靠左的区间进行匹配。
这样的复杂度是 $ O(nc) $ 的，~~听说有人过了~~，但这样的解法其实还有很大优化空间。
我们将区间按左端点为关键字排序，建立一个以右端点为关键字的小根堆。
对于每个 $ T_i $，我们将所有左端点小于 $ T_i $ 的区间插入堆（这些区间都将成为候选的可安排区间），接着将所有右端点小于 $ T_i $ 的区间从堆中弹出（因为 $ T_i $ 递增，未来这些区间也不可能被安排）。
执行完上面几步后，堆顶的区间正满足上面朴素做法中的“满足条件且右端点最靠左的区间”，可以与当前 $ T_i $ 匹配。
该算法的复杂度是 $ O(n \log n) $。
```cpp
#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;
}
```