题解 AT2645 【[ARC076D] Exhausted?】
ez_lcw
2020-10-22 14:09:57
~~一开始想的是线段树优化建图网络流。~~
但是看到 $n\leq10^5$ 就知道不可能了。
然后又尝试了一种错误的贪心:(这也是大多数人会想到的但是错误的贪心)
先将所有的 $(l_i,r_i)$ 按 $l_i$ 从小到大排序,其中 $l_i$ 相同的按 $r_i$ 从大到小排序。
然后从 $1$ 到 $n$ 扫每个人的要求,假设当前是第 $i$ 个人,那么我们就找到满足位置 $\leq l_i$ 且最靠右的那个椅子上;如果找不到,就找到满足位置 $\geq r_i$ 且最靠左的那个椅子上;如果还是找不到,那么这个人的需求就不能被满足。
但是发现这种方法会被一种情况 hack 掉:
```
3 4
1 3
2 5
2 5
```
用图来表示就是这样:(其中 ①②③ 代表的是排序后的每一个要求)
![](https://cdn.luogu.com.cn/upload/image_hosting/no9ynpv3.png)
按照我们刚才的贪心,我们会把第 $1$ 个人放在第 $1$ 个位置,把第 $2$ 个人放在第 $2$ 个位置,然后第 $3$ 个人没有位置放,所以答案是 $1$。(如上图)
虽然看起来很正确,但是你发现还有一种更优的解法,如图:
![](https://cdn.luogu.com.cn/upload/image_hosting/8itfjdi8.png)
那么我们需要考虑如何避免这样的问题。
重新考虑开始的过程:从 $1$ 到 $n$ 扫每个人的要求,假设当前是第 $i$ 个人。
寻找满足位置 $\leq l_i$ 且最靠右的那个椅子,如果找到了的话:
显然,如果出现了刚刚的那种情况,那么我们就让另一个人坐这个椅子;如果没有出现,那么我们不如就让 $i$ 坐这个椅子。
所以不管有没有出现刚刚那种情况,这张椅子肯定是会被坐的。
那么我们先不妨假设 $i$ 坐上了这张椅子,然后遍历后面的某一个人 $j$ 的时候,如果在 $\leq l_j$ 的范围中找不到可以坐的椅子了,那么我们就看需不需要让 $i$ “反悔”,让 $j$ 坐 $i$ 坐着的这张椅子,$i$ 另外去 $\geq r_i$ 的地方找椅子。(注意排序过后 $l_i\leq l_j$,所以 $i$ 坐着的椅子 $j$ 肯定也能坐)
如何维护“反悔”这么一个操作?
我们可以设置一个小根堆,然后每次当 $i$ 找到 $\leq l_i$ 可以坐的椅子,然后在小根堆中插入 $r_i$,表示 $i$ 坐在了 $\leq l_i$ 的某一个位置,而且 $i$ 可以“反悔”——换到 $\geq r_i$ 的某一个空位。
但如果 $i$ 在 $\leq l_i$ 的位置中找不到可以坐的椅子,我们有两种选择:(假设当前小根堆的堆顶是 $r_j$)
1. 如果 $r_j\leq r_i$,那么肯定是让 $j$ 从位置 $\leq l_j$ 换到位置 $\geq r_j$ 更优,然后让 $i$ 坐 $j$ 本来坐着的那张椅子。
1. 如果 $r_j>r_i$,那么还不如让 $i$ 坐在 $\geq r_i$ 的那个位置。
那么我们通过这种方式就能安排好每一个人 $i$ 到底是坐在 $\leq l_i$ 还是 $\geq r_i$ 的位置了。
至于这时如何统计答案,可以直接用 $O(n\log n)$ 排序,当然也可以直接 $O(n)$ 做,具体做法见代码。
代码如下:
```cpp
#include<bits/stdc++.h>
#define N 200010
using namespace std;
struct Question
{
int l,r;
}a[N];
int n,m,ans;
int b[N],c[N];
priority_queue<int,vector<int>,greater<int> >q;
bool cmp(Question a,Question b)
{
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
int tot=0;
for(int i=1;i<=n;i++)
{
if(!a[i].l)
{
c[a[i].r]++;
continue;
}
if(tot==a[i].l)
{
int u=q.top();
if(u<=a[i].r)
{
q.pop();
c[u]++;
q.push(a[i].r);
}
else c[a[i].r]++;
continue;
}
++tot;
b[tot]++;
q.push(a[i].r);
}
//记录的数组b、c分别表示哪些位置要填<=li,哪些位置要填>=ri,然后直接动态记录答案就好了:
int ltmp=0;
ans+=b[0],b[m]+=b[m+1];
for(int i=1;i<=m;i++)
{
if(i-ltmp>=b[i])
{
ltmp+=b[i];
continue;
}
ans+=b[i]-(i-ltmp);
ltmp=i;
}
int rtmp=m+1;
ans+=c[m+1],c[1]+=c[0];
for(int i=m;i>=ltmp+1;i--)
{
if(rtmp-i>=c[i])
{
rtmp-=c[i];
continue;
}
ans+=c[i]-(rtmp-i);
rtmp=i;
}
for(int i=ltmp;i>=1;i--)
{
if(rtmp-(ltmp+1)>=c[i])
{
rtmp-=c[i];
continue;
}
ans+=c[i]-(rtmp-(ltmp+1));
rtmp=ltmp+1;
}
printf("%d\n",ans);
return 0;
}
/*
3 4
1 3
2 5
2 5
*/
```