企业官网建设流程全解析

题目大意

机场一共有 n 个廊桥，可以分配一部分给国内区，剩下给国际区。
国内航班只能使用国内区廊桥，国际航班只能使用国际区廊桥。飞机严格按照抵达时间先后到达，遵循先到先得：

1. 如果本区还有空闲廊桥，则占用廊桥停靠；
2. 没有空闲廊桥就停靠远机位。远机位数量无限。
   给定所有国内、国际航班的抵达、离开时刻，请你把 n 个廊桥划分给国内和国际，求能够停靠廊桥的飞机数量的最大值。

解题思路

这道题有点像力扣上的“会议室安排”。使用小根堆维护正在被占用廊桥的飞机的离开时间。

处理每一架航班[l,r]：

1. 将堆中所有离开时间小于l的元素弹出，代表飞机飞走，廊桥释放；
2. 如果堆内元素数量小于 k，代表还有空闲廊桥：该飞机停靠廊桥，将离开时间入堆，计数 + 1；
3. 否则没有廊桥可用，去远机位。

暴力做法：枚举国内分配 i 个廊桥，国际分配n-i个廊桥，对每一个 i 都完整模拟一遍航班。
暴力超时的原因：对于不同的廊桥数量，重复模拟同一批航班，大量重复运算。

优化

我们希望只模拟一次全部 n 个廊桥，直接得到分配每个廊桥对应的答案。给廊桥编号1,2,3…n，遵循规则：每次优先选择编号最小的空闲廊桥。
维护两个堆：

1. b_id：小根堆，存储 pair (飞机离开时间，廊桥编号)，记录哪些廊桥正在被占用；
2. q_id：小根堆，存储空闲廊桥的编号。

模拟过程：

1. 初始化，1到n全部廊桥放入空闲堆；
2. 遍历每一个航班，先把已经飞走的飞机对应的廊桥释放，归还到空闲编号堆；
3. 如果存在空闲廊桥，取出编号最小的廊桥给当前航班，记录这个廊桥承接了 1 架飞机；
4. res[id] 代表：编号为 id 的廊桥一共承接多少架飞机。

对res数组求前缀和，得到：
pd[x]：国内分配 x 个廊桥，可以停靠的飞机总数；
pg[x]：国际分配 x 个廊桥，可以停靠的飞机总数。
最后枚举所有分配方案：国内拿 i 个廊桥，国际拿n-i个廊桥，求
ans=max(ans,pd[i]+pg[n-i])(0<=i<=n)

#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;intn,m1,m2;vector<int>js(vector<pair<int,int>>&v,intk){vector<int>res(k+1,0);priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>b_id;//廊桥的编号和离开时间priority_queue<int,vector<int>,greater<int>>q_id;//空闲的廊桥编号for(inti=1;i<=k;i++){q_id.push(i);}for(inti=0;i<v.size();i++){intl=v[i].first;intr=v[i].second;// 释放已经离开的飞机，归还廊桥编号while(!b_id.empty()&&b_id.top().first<=l){intid=b_id.top().second;b_id.pop();q_id.push(id);}if(q_id.empty()){continue;}intid=q_id.top();q_id.pop();res[id]++;b_id.push({r,id});}returnres;}intmain(){cin>>n>>m1>>m2;vector<pair<int,int>>d(m1);vector<pair<int,int>>g(m2);for(inti=0;i<m1;i++){cin>>d[i].first>>d[i].second;}for(inti=0;i<m2;i++){cin>>g[i].first>>g[i].second;}sort(d.begin(),d.end());sort(g.begin(),g.end());intans=0;vector<int>cd=js(d,n);vector<int>cg=js(g,n);vector<int>pd(n+1,0),pg(n+1,0);//前缀和数组for(inti=0;i<=n;i++){pd[i]=pd[i-1]+cd[i];pg[i]=pg[i-1]+cg[i];}for(inti=0;i<=n;i++){ans=max(ans,pd[i]+pg[n-i]);}cout<<ans;return0;}