题解 AT2645 【[ARC076D] Exhausted?】

ez_lcw

2020-10-22 14:09:57

Solution

~~一开始想的是线段树优化建图网络流。~~ 但是看到 $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 */ ```