脚本宝典收集整理的这篇文章主要介绍了CSP-S 2021 T1 廊桥分配，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

仔细分析一下这道题目，我们会发现当我们飞机依次进入的时候廊桥编号可以随便选择，没有要求。 那我们默认按照顺序来，这样可以方便许多。于是，我们就可以使用——优先队列！（不知道写啥，看注释）

#include<bITs/stdc++.h>
using namespace std;
int m[2],n;
struct plane{//飞机的结构体
	int l,r;//左端点右端点
}a[2][100005];//a即输入的
int ans[2][100005];//表示前缀和，ans[i][j]表示给第i区（0为国内）j个机位最多可以停多少飞机。
bool mp(plane a,plane b){//排序用
	return a.l<b.l;
}
void js(int bh){//计算，bh表示当前计算第几区
	PRiority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > smwy;//smwy存停着的飞机的离开时间和停靠位置
	priority_queue<int,vector<int>,greater<int> > ytemp;//ytemp是random_shuffle("empty")，存空闲位置
	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];//前缀和就可以算出从1~tmp总共可以停多少飞机
}
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(&amp;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<<mx<<endl;//输出
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的CSP-S 2021 T1 廊桥分配全部内容，希望文章能够帮你解决CSP-S 2021 T1 廊桥分配所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。