专栏文章

题解：AT_arc076_d [ARC076F] Exhausted?

hhoko
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miohkqbx
此快照首次捕获于
2025/12/02 19:20
3 个月前
此快照最后确认于
2025/12/02 19:20
3 个月前
查看原文

题目传送门

题目大意

给出 mm 把椅子，排在数轴 1∼m1\sim m 的位置上，有 nn 个人，每个人对自己坐的位置有要求，这个人不能坐在 li∼ril_i\sim r_i 的位置上，其余都可。

题目分析

首先我们考虑贪心，我们先考虑只有一条限制的情况，就是一个人要么只能坐在 −∞∼li-\infin \sim l_i 或者坐在 ri∼+∞r_i \sim +\infin 的位置上。容易想到对 lil_i 或者 rir_i 进行排序，然后从限制最严的人开始往后扫，如果这个人可以坐在这个位置上，那么就把我们还有椅子的区间缩减，如果这个人没位置坐了，那么答案加一。
现在我们加上另一条限制，单纯的排序再排座位不一定最优了，所以我们考虑反悔贪心。先按左端点从小到大排序，如果有座位那就把他放到目前区间的最左端，然后把左端点加一。如果这个人没座位了，他不一定右端点比较小，不一定最优，所以我们要把之前放到左边座位上的人的右端点最小的那个人踢出来，把当前这个人放到那个座位上，踢出来这个人因为他的右端点目前最小，所以把他放到右边的座位上局部最优。
这一段可以用小根堆来处理，小根堆记录的是右端点，每次踢出来右端点最小的那个。
之后我们再把要放到右边的那些人按右端点从大到小排序，同理左端点的贪心处理，不过如果这次有人没位置坐的话，就只能给他加椅子，所以就答案加一。
代码如下：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
ll n,m,cnt,tmp[N],ans;
struct node{ll l,r;} s[N];
bool cmp(node a,node b){return a.l<b.l;}
priority_queue<ll,vector<ll>,greater<ll> > q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>s[i].l>>s[i].r;
    sort(s+1,s+n+1,cmp);
    ll h=1,t=m;
    for(int i=1;i<=n;i++){
        q.push(s[i].r);
        if(h<=s[i].l&&h<=t)h++;
        else{
            tmp[++cnt]=q.top();
            q.pop();
        }
    }
    sort(tmp+1,tmp+cnt+1);
    for(int i=cnt;i>=1;i--){
        if(tmp[i]<=t&&t>=h)t--;
        else ans++;
    }
    cout<<ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...