2021年CSP-S提高组第二轮竞赛第一题：廊桥分配。
首先先把题目放出来：
当一架飞机抵达机场时， 可以停靠在航站楼旁的廊桥， 也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥， 因为这样省去了坐摆渡车前往航站楼的周折。
然而， 因为廊桥的数量有限， 所以这样的愿望不总是能实现。
机场分为国内区和国际区， 国内航班飞机只能停靠在国内区， 国际航班飞机只能停靠在国际区。一部分廊桥属于国内区， 其余的廊桥属于国际区。
L 市新建了一座机场， 一共有n个廊桥。该机场决定， 廊桥的使用遵循“ 先到先得”
的原则， 即每架飞机抵达后， 如果相应的区（ 国内/ 国际） 还有空闲的廊桥， 就停靠在廊桥， 否则停靠在远机位（ 假设远机位的数量充足） 。该机场只有一条跑道， 因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻， 请你负责将n个廊桥分配给国内区和
国际区， 使停靠廊桥的飞机数量最多。
开始整理思路：
如果你是追求满分的选手，请直接拉到第三个思路。
第一个思路：从0分到20分（二维数组不排序完成）
本思路完全占在非常基础的角度思考问题，可以说是全网最低解题得分的方案，虽然拿不到那么高的分数，但是一个题目拿到基础数据分数也是不小的提升。
对于一个初学者或者刚接触竞赛的选手，我们第一想到的是使用二维数组完成题目。因为国内和国际规则相同，数据独立，因此需要两个二维数组记录数据。
下面我们进行解题，要分配廊桥，我们可以通过自己模拟数据得到，如果有n个廊桥，一共有n+1个分配方案，因此我们要一条一条的计算，最终取最大的那个结果。因为考虑到分配0有特殊性，减少一定计算，我们单独判断单独处理。
每次计算的时候，因为我们不排序，因此需要一个循环从飞机入场时间中找到最小的时间，找到后记录位置，然后记录停放次数。停放的个数也是不定长，因此也要数组去记录每个飞机离开的时间，真实模拟竞赛给到的数据和环境，最终20分方案如下：
#include
using namespace std;
int main()
{
//用二维数组不排序 ,20分
int n,m1,m2;
cin>>n>>m1>>m2;
int nei2[m1][2];
int wai2[m2][2];
for(int i=0;i>nei2[i][0];
cin>>nei2[i][1];
}
for(int i=0;i>wai2[i][0];
cin>>wai2[i][1];
}
//定义结果，取所有分配中最大的
int jg=0;
//循环n-1次，区分国内国外的廊桥分配，k表示国内的个数
//两边都是0的情况特殊判断
for(int k=1;k 思路2：从0分到35分
此题明显是要使用排序的处理方式更加方便，因此知道如何二维数组排序或者变成结构体排序的话会方便很多，依然是刚才思路1的解题方式，简化程序，提升效率，顺利的从20分提升到了35分。完整程序如下：
#include
using namespace std;
struct lang{
int in;
int out;
};
bool cmp(lang l1,lang l2)
{
return l1.in>n>>m1>>m2;
lang nei[m1],wai[m2];
for(int i=0;i>nei[i].in;
cin>>nei[i].out;
}
for(int i=0;i>wai[i].in;
cin>>wai[i].out;
}
sort(nei,nei+m1,cmp);
sort(wai,wai+m2,cmp);
int jg=0;
for(int k=1;ka[j])
{
a[j]=nei[i].out;
ci++;
break;
}
}
}
int a2[n-k]={0};
for(int i=0;ia2[j])
{
a2[j]=wai[i].out;
ci++;
break;
}
}
}
jg=max(jg,ci);
}
int ci=0;
int a[n]={0};
for(int i=0;ia[j])
{
a[j]=nei[i].out;
ci++;
break;
}
}
}
jg=max(jg,ci);
ci=0;
for(int i=0;ia[j])
{
a[j]=wai[i].out;
ci++;
break;
}
}
}
jg=max(jg,ci);
cout< 思路2优化：提升效率
本想着用二维数组或者结构体终结这个题，发现坑比较深，虽然优化版本提升了效率，但是并没有实质性的改变效率，因为此题的数据量还是不小。说下思路。
我们先通过一次排序把廊桥停机离开时间从小到大排列好，然后每次去掉第一位上的飞机，后面的飞机按排队的方式插入到合适的位置保证每次进来后停机的数组都是有序的，不用从0到尾遍历数据找合适的飞机。最终还是拿下35分，优化后的程序如下：
#include
using namespace std;
struct lang{
int in;
int out;
};
bool cmp(lang l1,lang l2)
{
return l1.in>n>>m1>>m2;
lang nei[m1],wai[m2];
for(int i=0;i>nei[i].in;
cin>>nei[i].out;
}
for(int i=0;i>wai[i].in;
cin>>wai[i].out;
}
sort(nei,nei+m1,cmp);
sort(wai,wai+m2,cmp);
int jg=0;
vector a,a2;
for(int k=1;ka[0])
{
a.erase(a.begin());
if(a.size()==0)
{
a.push_back(nei[i].out);
ci++;
continue;
}
int fan=0;
for(int j=0;ja2[0])
{
a2.erase(a2.begin());
if(a2.size()==0)
{
a2.push_back(wai[i].out);
ci++;
continue;
}
int fan=0;
for(int j=0;j an;
an.clear();
for(int i=0;ian[0])
{
an.erase(an.begin());
int fan=0;
for(int j=0;j aw;
for(int i=0;iaw[0])
{
aw.erase(aw.begin());
int fan=0;
for(int j=0;j 思路3：优先队列（100分满分方案）
其实按照思路2的方式，把3层循环改成2层循环即可，唯一能去掉的循环就是插入排序的那个循环，我们把vector换成优先队列即可。此方案是我从其他人借鉴过来的，稍作改动，也给大家看看不同风格的程序，保留了一部分原作者的结构，做了注释。前缀和的思路其实并没有本质性提升效率，而是通过优先队列解决了大问题。完整程序如下：
#include
using namespace std;
//对于大数据处理，一个是二分法，一个是前缀和
int m[2],n;
struct plane{
int l,r;
}a[2][100000];
int ans[2][100001];//记录前缀和
bool mp(plane a,plane b){
return a.l,vector >,greater > > smwy;
//ytemp是random_shuffle("empty")，存空闲位置
priority_queue,greater > ytemp;
for(int i=1;i<=n;i++) ytemp.push(i);
for(int i=1;i<=m[bh];i++){//先到先得
while(!smwy.empty()&&a[bh][i].l>=smwy.top().first){
ytemp.push(smwy.top().second);
smwy.pop();
}
if(ytemp.empty()) continue;//没有空位了
int tmp=ytemp.top();//最小的
ans[bh][tmp]++;
smwy.push(make_pair(a[bh][i].r,tmp));
ytemp.pop();
//tmp这个位置需要一个
//push把飞机加入停着的优先队列里
//pop就是说明这个地方没有空位了
}
for(int i=1;i<=n;i++)
ans[bh][i]+=ans[bh][i-1];
}
int main(){
cin>>n>>m[0]>>m[1];
for(int i=1;i<=m[0];i++)
cin>>a[0][i].l>>a[0][i].r;
for(int i=1;i<=m[1];i++)
cin>>a[1][i].l>>a[1][i].r;
sort(&a[0][0],&a[0][m[0]+1],mp);
sort(&a[1][0],&a[1][m[1]+1],mp);
js(0);
js(1);
int mx=-1;
for(int i=0;i<=n;i++)
mx=max(mx,ans[0][i]+ans[1][n-i]);
cout<