题意：

给你m个椅子可以坐人，初始坐标为正整数1~m，有n个人，每个人希望坐的位置$\leq L_i$或者$\geq R_i$，可以添加若干个椅子在任意的实数位置，求最少要添加多少椅子使得所有人都有位置坐？

$1\leq n,m\leq 2\times 10^5$

$0\leq L_i<R_i\leq m+1$

题解：

这题其实有一个显然的网络流解法，但是直接建图会爆，用线段树优化建图可以过，写的会很麻烦。。。（Orzckw）

场上dalao们八仙过海以不同的姿势各种贪心水到了大量分数。。。

正解是一个优秀的贪心。考虑只有一边的限制（比如只有$L$），那么显然的贪心是，从左到右枚举每个椅子，在$L_i$处决定每个人坐在哪，然后每向后一个椅子就能多放一个，考虑有多少人左端点在当前枚举到的椅子，能放就尽量放，多的就不放，并将空位设为0；

加上$R$的条件其实类似，把每个人记录在$L$上，然后能放就尽量放，遇到放不下的情况时可以考虑用新的这个人代替掉原来的人，条件是他的$R$比原来的人的$R$要大，这样可以保证换出来的人更容易重新放进去。那么用小根堆维护$R$，然后扫一遍即可；

枚举完把放好的人拎到一边，反着做一次只考虑$R$的贪心，即可求出答案。

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 using namespace std;

 struct task{

     int l,r;

 }a[];

 priority_queue<int>q;

 pair<int,int>pi[];

 bool cmp(task a,task b){

     return a.l==b.l?a.r<b.r:a.l<b.l;

 }

 int n,m,l,r,tot=,ans=,now[];

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);

     sort(a+,a+n+,cmp);

     l=,r=m;

     for(int i=;i<=n;i++){

         q.push(-a[i].r);

         if(l<=r&&l<=a[i].l)l++;

         else{

             now[++tot]=-q.top();

             q.pop();

         }

     }

     sort(now+,now+tot+);

     for(int i=tot;i;i--){

         if(l<=r&&r>=now[i])r--;

         else ans++;

     }

     printf("%d",ans);

     return ;

 }

巴特西

[arc076f]Exhausted? - 贪心

题意：

题解：

最新文章

热门文章