1 solutions

  • 0
    @ 2026-8-27 21:30:30
    #include<bits/stdc++.h>
    using namespace std;
    #define x first
    #define y second
    typedef pair<int,int> PII;
    const int N=100010;
    int n,m1,m2;
    PII q1[N],q2[N];
    int s1[N],s2[N];
    void calc(int m,PII q[],int s[])
    {
    	sort(q,q+m); //按照到达的先后顺序从小到达排序
    	priority_queue<int,vector<int>,greater<int>> idle; //空闲的廊桥(按照廊桥的编号从小到达排序)
    	priority_queue<PII,vector<PII>,greater<PII>> full; //已经占用的廊桥(按照飞机离开的时间从小到大排序)
    	for(int i=1;i<=n;i++) idle.push(i);
    	for(int i=0;i<m;i++) //枚举每个飞机
    	{
    		int st=q[i].x,ed=q[i].y; //获取到达时间和离开时间
    		while(full.size()&&full.top().x<st)  //弹出这个飞机后面相对空闲的廊桥
    		{
    			idle.push(full.top().y); //这个廊桥是空闲的了
    			full.pop();	 //弹出廊桥
    		}
    		if(idle.empty()) continue; //这个飞机找不到廊桥
    		int t=idle.top(); //找到编号最小的空闲的廊桥
    		idle.pop(); //弹出空闲
    		s[t]++; //数量增加
    		full.push({ed,t}); //增加一个占用的廊桥
    	} 
    	for(int i=1;i<=n;i++) //预处理前缀和
    	{
    		s[i]+=s[i-1];
    	}
    } 
    int main()
    {
    	cin>>n>>m1>>m2;
    	for(int i=0;i<m1;i++)
    	{
    		cin>>q1[i].x>>q1[i].y;
    	}
    	for(int i=0;i<m2;i++)
    	{
    		cin>>q2[i].x>>q2[i].y;
    	}
    	calc(m1,q1,s1); //国内航班的模拟
    	calc(m2,q2,s2); //国外航班的模拟
    	int res=0;
    	for(int i=0;i<=n;i++) //枚举廊桥的分类
    	{
    		res=max(res,s1[i]+s2[n-i]);
    	}
    	cout<<res;
    	return 0;
    }
    
    • 1

    Information

    ID
    1146
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    9
    Accepted
    2
    Uploaded By