CSP-S2021 题解

__vector__ · 2022-07-26 22:51:46 · 个人记录

题外话

这是某蒟蒻为了 CSP-S2022 不爆零做的一点挣扎。

廊桥分配

做法

一个简单的思路就是枚举分配给国内航班和国际航班的航班数量，然后每枚举一种情况 O(n) 计算答案，最后取最大值，总复杂度 O(n^2)。

想一想能不能对计算答案进行优化。

显然，设分配了 i 个廊桥，那么答案等于这 i 个廊桥分别有多少飞机停靠。

一个比较显然的结论是，当廊桥数量增加时，如果强制飞机进入编号最小的空闲廊桥，那么原来去哪个廊桥的飞机还去哪个廊桥。

所以，可以先预处理出在假设廊桥充足的情况下，每个廊桥有多少飞机停靠。

然后做个前缀和，前缀和数组第 i 个元素表示如果有 i 个廊桥，那么答案是多少。

枚举分配廊桥数量取最大值就行了。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    int n,m1,m2;
    struct Plane
    {
        int a,b;
    }pl[maxn],pl2[maxn];
    bool cmp(Plane a,Plane b)
    {
        return a.a<b.a;
    }
    int qzh[maxn],qzh2[maxn];
    void calc1()
    {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> lk;
        //待离开飞机队列
        //pair的第一个元素是离开时间，第二个是占用的廊桥编号
        priority_queue<int,vector<int>,greater<int>> lq;
        //空闲廊桥队列
        for(int i=1;i<=n;i++)
        {
            lq.push(i);
        }//初始所有廊桥都是空的
        for(int i=1;i<=m1;i++)
        {
            while(!lk.empty()&&lk.top().first<pl[i].a)//将第 i 架飞机到达前已经离开的飞机清除并释放廊桥
            {
                lq.push(lk.top().second);
                lk.pop();
                //飞机离开，释放廊桥
            }
            if(lq.empty())continue;
            int used=lq.top();//当前飞机使用的廊桥编号
            qzh[used]++;
            lq.pop();
            lk.push(make_pair(pl[i].b,used));
        }
        for(int i=1;i<=n;i++)
        {
            qzh[i]=qzh[i-1]+qzh[i];
        }
    }
    void calc2()
    {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> lk;
        //待离开飞机队列
        //pair的第一个元素是离开时间，第二个是占用的廊桥编号
        priority_queue<int,vector<int>,greater<int>> lq;
        //空闲廊桥队列
        for(int i=1;i<=n;i++)
        {
            lq.push(i);
        }//初始所有廊桥都是空的
        for(int i=1;i<=m2;i++)
        {
            while(!lk.empty()&&lk.top().first<pl2[i].a)//将第 i 架飞机到达前已经离开的飞机清除并释放廊桥
            {
                lq.push(lk.top().second);
                lk.pop();
                //飞机离开，释放廊桥
            }
            if(lq.empty())continue;
            int used=lq.top();//当前飞机使用的廊桥编号
            qzh2[used]++;
            lq.pop();
            lk.push(make_pair(pl2[i].b,used));
        }
        for(int i=1;i<=n;i++)
        {
            qzh2[i]=qzh2[i-1]+qzh2[i];
        }
    }
    void main()
    {
        scanf("%d%d%d",&n,&m1,&m2);
        for(int i=1;i<=m1;i++)
        {
            scanf("%d%d",&pl[i].a,&pl[i].b);
        }
        for(int i=1;i<=m2;i++)
        {
            scanf("%d%d",&pl2[i].a,&pl2[i].b);
        }
        sort(pl+1,pl+m1+1,cmp);
        sort(pl2+1,pl2+m2+1,cmp);
        calc1();
        calc2();
        int ans=0;
        for(int i=0;i<=n;i++)
        {
            ans=max(ans,qzh[i]+qzh2[n-i]);
        }
        printf("%d",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}

其他 3 题

还没做。