[arc076F]Exhausted? 贪心+堆-白红宇

[arc076F]Exhausted? 贪心+堆

阅读量：5114 次

发布时间：2019-06-13

本文共 1035 字，大约阅读时间需要 3 分钟。

Description

有m个椅子，第i个在位置i，每个椅子只能坐一个人。有n个人，第i个人能坐的椅子的位置j需满足j≤Li或j≥Ri。现在你可以添加若干个椅子，可以放在任意实数位置。问最少加多少个

Input

第一行两个整数N,MN,M

接下来NN行，每行两个整数Li,RiLi,Ri

Output

输出最小需要增加的数量

Sample Input

Case 1:4 40 32 31 33 4Case 2:7 60 71 53 62 71 62 63 7Case 3:3 11 21 21 2Case 4:6 61 61 61 51 52 62 6

Sample Output

Case 1:0Case 2:2Case 3:2Case 4:2

HINT

1≤N,M≤2∗1051≤N,M≤2∗105

0≤Li<Ri≤M+1(1≤i≤N)0≤Li<Ri≤M+1(1≤i≤N)

所有输入的数都是正整数

Sol

我们把左端点排序，然后用一个堆维护左边安排不下的人的r，每次如果还有空位置就直接放，没有的话就把堆里最大值和现在作比较，选择大的安排座位，小的放堆里

之后右边按顺序安排即可。

Code

#include 
    
     using namespace std;int n,m,L,R,hr[200005],ans;priority_queue
     
      
       ,greater
       
         >h;vector
        
         hl[200005];char c;int main(){    scanf("%d%d",&n,&m);    for(int i=0,l,r;i

::iterator it=hl[i].begin();it!=hl[i].end();it++) { if(L

=*it) hr[*it]++; else h.pop(),hr[t]++,h.push(*it); } for(vector

::iterator it=hl[0].begin();it!=hl[0].end();it++) hr[*it]++; R=m+1;ans=hr[m+1]; for(int i=m;i;i--) for(;hr[i]>0;hr[i]--) if(i

转载于:https://www.cnblogs.com/CK6100LGEV2/p/9506546.html

你可能感兴趣的文章