题目大意机场一共有 n 个廊桥可以分配一部分给国内区剩下给国际区。国内航班只能使用国内区廊桥国际航班只能使用国际区廊桥。飞机严格按照抵达时间先后到达遵循先到先得如果本区还有空闲廊桥则占用廊桥停靠没有空闲廊桥就停靠远机位。远机位数量无限。给定所有国内、国际航班的抵达、离开时刻请你把 n 个廊桥划分给国内和国际求能够停靠廊桥的飞机数量的最大值。解题思路这道题有点像力扣上的“会议室安排”。使用小根堆维护正在被占用廊桥的飞机的离开时间。处理每一架航班[l,r]将堆中所有离开时间小于l的元素弹出代表飞机飞走廊桥释放如果堆内元素数量小于 k代表还有空闲廊桥该飞机停靠廊桥将离开时间入堆计数 1否则没有廊桥可用去远机位。暴力做法枚举国内分配 i 个廊桥国际分配n-i个廊桥对每一个 i 都完整模拟一遍航班。暴力超时的原因对于不同的廊桥数量重复模拟同一批航班大量重复运算。优化我们希望只模拟一次全部 n 个廊桥直接得到分配每个廊桥对应的答案。给廊桥编号1,2,3…n遵循规则每次优先选择编号最小的空闲廊桥。维护两个堆b_id小根堆存储 pair (飞机离开时间廊桥编号)记录哪些廊桥正在被占用q_id小根堆存储空闲廊桥的编号。模拟过程初始化1到n全部廊桥放入空闲堆遍历每一个航班先把已经飞走的飞机对应的廊桥释放归还到空闲编号堆如果存在空闲廊桥取出编号最小的廊桥给当前航班记录这个廊桥承接了 1 架飞机res[id] 代表编号为 id 的廊桥一共承接多少架飞机。对res数组求前缀和得到pd[x]国内分配 x 个廊桥可以停靠的飞机总数pg[x]国际分配 x 个廊桥可以停靠的飞机总数。最后枚举所有分配方案国内拿 i 个廊桥国际拿n-i个廊桥求ansmax(ans,pd[i]pg[n-i])(0in)#includeiostream#includealgorithm#includequeueusingnamespacestd;intn,m1,m2;vectorintjs(vectorpairint,intv,intk){vectorintres(k1,0);priority_queuepairint,int,vectorpairint,int,greaterpairint,intb_id;//廊桥的编号和离开时间priority_queueint,vectorint,greaterintq_id;//空闲的廊桥编号for(inti1;ik;i){q_id.push(i);}for(inti0;iv.size();i){intlv[i].first;intrv[i].second;// 释放已经离开的飞机归还廊桥编号while(!b_id.empty()b_id.top().firstl){intidb_id.top().second;b_id.pop();q_id.push(id);}if(q_id.empty()){continue;}intidq_id.top();q_id.pop();res[id];b_id.push({r,id});}returnres;}intmain(){cinnm1m2;vectorpairint,intd(m1);vectorpairint,intg(m2);for(inti0;im1;i){cind[i].firstd[i].second;}for(inti0;im2;i){cing[i].firstg[i].second;}sort(d.begin(),d.end());sort(g.begin(),g.end());intans0;vectorintcdjs(d,n);vectorintcgjs(g,n);vectorintpd(n1,0),pg(n1,0);//前缀和数组for(inti0;in;i){pd[i]pd[i-1]cd[i];pg[i]pg[i-1]cg[i];}for(inti0;in;i){ansmax(ans,pd[i]pg[n-i]);}coutans;return0;}