Atcoder [arc076F] Exhausted

2024-04-30 23:08

文章标签 atcoder exhausted arc076f

本文主要是介绍Atcoder [arc076F] Exhausted，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

机房里有M台电脑排成一排，第i台电脑的坐标是正整数i。

现在有N个OIer进入了机房，每个OIer需要一台电脑来学tui习ji，同时每个OIer对自己电脑所处的坐标范围有一个要求区间。第i个OIer希望自己的电脑的位置≤Li或≥Ri。自然，一台电脑只能给一个OIer使用，不然会发生友♂好的跤♂流

显然，有可能这个机房无法满足所有OIer的需求。这时老师就会在机房中增加电脑。增加的电脑可以位于任意的实数位置。你需要帮老师计算一下，老师最少加几台电脑，才可以满足所有OIer的需求？

Input

    第一行两个整数N,M接下来N行，每行两个整数Li,Ri

Output

    输出最小需要增加的电脑数量

Solution

贪心。
将询问按l,r作为第一、二关键字从小到大排序。
优先插进左端点，并恰好插满左端点(不能大于查询的l)
占据左边的端点的询问的丢进小根堆的优先队列。
记录一个tot表示用了1到tot号电脑。

若tot小于 $L_i$ ，直接丢进优先队列。
若tot等于 $L_i$ ，将优先队列中右端点最小的弹出来扔到右边。

因为记录的是向右的标记(>=x)
最后从后往前ans=max(ans,后缀和-后面已有的电脑数)

Code

#include<bits/stdc++.h>
using namespace std;
struct data{int l,r;bool operator <(const data &v)const{if(l!=v.l) return l<v.l;return r<v.r;}
}a[200010];
priority_queue<int>q;
int b[200010],n,m;
int main(){int x,y,tot=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);for(int i=1;i<=m;i++) b[i]=-1;sort(a+1,a+n+1);for(int i=1;i<=n;i++){//cout<<i<<" "<<a[i].l<<" "<<a[i].r<<" "<<q.size()<<endl;if(a[i].l==0){b[a[i].r]++; continue;}if(a[i].l==tot){int x=q.top();q.pop();//cout<<"kk"<<u.l<<" "<<u.r<<" "<<b[u.l]<<" "<<b[u.r]<<endl;b[-x]++;q.push(-a[i].r);continue;}//cout<<"sss"<<a[i].l<<" "<<b[a[i].l]<<endl;b[++tot]++;q.push(-a[i].r);}int ans=0,sum=0;for(int i=m+1;i>-1;i--){sum+=b[i];ans=max(ans,sum);//	cout<<b[i]<<endl;}printf("%d",ans);
}