洛谷 P7913 [CSP

题目描述请移步 https://www.luogu.com.cn/problem/P7913

• 题目简述

有一座机场，分为国际区和国外区，机场共有

n

m1

m2

a[i]

b[i]

对于每架飞机，若该区仍有廊桥空闲，就

必须

求将n个廊桥分配给国内区和国际区，停靠廊桥的飞机最多有多少架

• 题目分析

首先注意到飞机是有后效性的，先到达的飞机可能会占用一个廊桥直到它离开，因此需要对每架飞机按到达时间进行排序

遍历每架飞机复杂度为

O(m1+m2)

因此累加贡献部分的复杂度须为

O(log n)

• 解题思路

发现对于每架飞机，如果它在有 x 个廊桥时停靠廊桥，那么有 x+1 个廊桥时它必定停靠廊桥

假设 x=2 ，为方便，第i架飞机用 p[i] 来表示 不管数据具体是什么，这两个廊桥的使用必定与下图相似 廊桥1：p[1] --> p[3] -> p[4] ---------> p[9] 廊桥2：p[2] ---------------> p[7] （后面 “上一架飞机” 意为使用同一廊桥的上一架飞机） 每架飞机后面跟的都是首个到达时间比它离开时间晚的飞机（不考虑其他廊桥的占用） 若第 i 架飞机在两个廊桥时停靠廊桥，而三个廊桥时不停靠廊桥，则只可能其上一架飞机未停靠廊桥 以此类推，只有第 i 架飞机上一架的上一架... 即首个停靠原第 i 架飞机所停靠的廊桥的飞机未停靠廊桥，才可能成立 而新设一个廊桥并不影响原廊桥第一架停靠的飞机，因此这种情况不可能发生 

因此，每架飞机对答案的贡献，是一个 min_can~n 的区间（令 min_can 为最小的可让这架飞机停靠廊桥的廊桥数量）

考虑使用线段树、树状数组等 log n 级别的结构来解决

这是我们只需维护每架飞机的 "min_can" 就行了，这里分两种情况讨论

1.这架飞机(p[i])到达时有飞机(p[j])离开了，那么 min_can[x]=min_can[j]
2.这架飞机到达时没有飞机离开，则 min_can[x]=目前所有没离开的飞机的数量

要注意的是，一架飞机到达时可能有多架飞机离开，那么它之后的几架飞机仍可以从情况1转移

• 代码实现

#include <iostream> #include <utility> #include <algorithm> #include <cstring> #include <queue> #define int long long using namespace std; const int MAX=1e5+7; int n,m1,m2; pair <int,int> p1[MAX],p2[MAX];//飞机 //priority_queue升序 priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q1,q2;//<离开时间,第几架> priority_queue <int,vector<int>,greater<int> > mc1,mc2;//所有离开的飞机,维护并找到最小的min_can int min_can1[MAX],min_can2[MAX];//最少多少个廊桥才能使第i架飞机降落在廊桥 int tr1[MAX],tr2[MAX];//树状数组 int lowbit(int x){ return x&-x; } void add1(int pos){ for(int i=pos;i<=m1;i+=lowbit(i)){ tr1[i]++; } } void add2(int pos){ for(int i=pos;i<=m2;i+=lowbit(i)){ tr2[i]++; } } int query1(int pos){ int res=0; for(int i=pos;i>=1;i-=lowbit(i)){ res+=tr1[i]; } return res; } int query2(int pos){ int res=0; for(int i=pos;i>=1;i-=lowbit(i)){ res+=tr2[i]; } return res; } signed main(){ cin>>n>>m1>>m2; n=min(n,m1+m2); for(int i=1;i<=m1;i++){ cin>>p1[i].first>>p1[i].second; } for(int i=1;i<=m2;i++){ cin>>p2[i].first>>p2[i].second; } sort(p1+1,p1+m1+1); sort(p2+1,p2+m2+1);//按first升序 memset(min_can1,0x3f,sizeof(min_can1)); memset(min_can2,0x3f,sizeof(min_can2));//初始化极大值 for(int i=1;i<=m1;i++){ while(!q1.empty()&&q1.top().first<p1[i].first){ mc1.push(min_can1[q1.top().second]);//将离开的飞机的min_can值推入另一个优先队列 q1.pop(); } q1.push(make_pair(p1[i].second,i)); if(!mc1.empty()){//有未利用的离开的飞机 add1(mc1.top()); min_can1[i]=mc1.top(); mc1.pop(); }else{ add1(q1.size());//未离开的飞机的数量 min_can1[i]=q1.size();//更改min_can的值 } } for(int i=1;i<=m2;i++){//同上 while(!q2.empty()&&q2.top().first<p2[i].first){ mc2.push(min_can2[q2.top().second]); q2.pop(); } q2.push(make_pair(p2[i].second,i)); if(!mc2.empty()){ add2(mc2.top()); min_can2[i]=mc2.top(); mc2.pop(); }else{ add2(q2.size()); min_can2[i]=q2.size(); } } int ans=-1; for(int i=0;i<=n;i++){ ans=max(ans,query1(i)+query2(n-i));//合并答案 } cout<<ans; } 

完结撒花qwq