【AtCoder Regular Contest 076 F】Exhausted? | Mrsrz's blog

贪心。

题目大意：

有 $m$ 个椅子，编号 $1\sim m$。有 $n$ 个人，每个人有一个限制 $l_i,r_i$，表示他坐的椅子的编号要么 $\leq l_i$，要么 $\geq r_i$。

可以继续加椅子，编号向上累加。

问至少添加多少椅子，才能使所有人都有椅子坐。

题解：

贪心。

我们首先按照 $l_i$ 排序，然后从小到大安排座位，这样保证编号小的座位尽可能坐满。

然后考虑新插进一个人。这个时候之前已经占用的位置他都一定可以坐到。

如果还有空位，则直接安排到任意一个空位（因为 $l_i$ 单调所以前面的空位对于后面的人来说都可以坐到）。

如果没有空位，我们考虑能不能把一个人踢掉。

对于左边的位置来说，踢掉一个人并且换上没有影响。所以我们要最大化右边的贡献。

那么我们显然踢掉一个 $r_i$ 尽可能小的，因为他在右边的选择空间大。

所以我们用一个堆维护左边的位置的人，以 $r_i$ 为关键字，每次如果要踢就直接把堆顶弹出来，放到维护右边位置的东西里即可。

最后再对被踢的人按照 $r_i$ 排序做个贪心即可。

两边不相交的情况下，不会产生冲突，这样最大化了两边的位置，显然是最优的。

两边相交时，说明所有位置都坐满了，也是最优的。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
pair<int,int>A[233333];int n,m,d;
priority_queue<int,vector<int>,greater<int>>q,v;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d%d",&A[i].first,&A[i].second);
    sort(A+1,A+n+1);
    for(int i=d=1;i<=n;++i)if(d<=m&&A[i].first>=d)q.push(A[i].second),++d;else q.push(A[i].second),v.push(q.top()),q.pop();
    for(int i=d;i<=m&&!v.empty();++i)if(i>=v.top())v.pop();
    printf("%d",v.size());return 0;
}