CSP-S 2021 T1 廊桥分配 (airport) 的另一种解法

lht64877586

    // 新人第一次发帖

    // 本帖首发于申请专区，因为难度系数太低所以未通过，今年暑假开放注册时才注册成功（555），仅提供一种思路（也是做个回忆）

    闲话不多说，进入正文：

    洛谷上的题解大多是优先队列、线段树、pair等，

    这里提供一种“无脑运算”的解法

    比赛时首先想的想到的是模拟，但超时。

    在模拟时发现“新加入廊桥可以视为原先的远机位的一部分”的重要结论，所以将远机位视为廊桥进行预处理，再枚举搜索最佳方案，得到结果。

预处理部分运用仿Windows消息处理的机制（个人认为既然是操作系统都在用的方法，一定很优秀）

上代码：（图片就免了~）

   

[C++] 纯文本查看 复制代码

/*
Score  100 AC
Memory 3.5 M  / 256  M
Time   220 ms / 1000 ms
采用非传统方法
灵感来自Windows的消息处理队列机制
预备结论：新加入廊桥可以视为原先的远机位的一部分
*/
#include <bits/stdc++.h>
using namespace std;
struct message
{
    int time;
    int plane;
}; //定义结构体——消息
message home_arrive[100010],home_leave[100010];
message abroad_arrive[100010],abroad_leave[100010]; //消息队列数组
int n, m1, m2;
int home, abroad; //国内国际廊桥总数
int home_bridge[100010], abroad_bridge[100010];//国内国际廊桥[i]的飞机数
int plane[100010];                              //飞机[i]使用的廊桥
bool home_bdg[100010], abroad_bdg[100010];      //国内国际廊桥是否被占用
void read()                                     //输入
{
    for (int i = 1; i <= m1; i++)
    {
        home_arrive[i].plane = home_leave[i].plane = i;            //飞机编号
        scanf("%d %d", &home_arrive[i].time, &home_leave[i].time); //输入
    }
    for (int i = 1; i <= m2; i++)
    {
        abroad_arrive[i].plane = abroad_leave[i].plane = i;            //飞机编号
        scanf("%d %d", &abroad_arrive[i].time, &abroad_leave[i].time); //输入
    }
}
bool msgcmp(message a, message b) //消息排序，形成队列
{
    return a.time < b.time;
}
void init() //分配
{
    int a, b, t = 1; // a，b代表消息队列头指针，t代表当前廊桥编号
    // 处理国内飞机
    a = b = 1; //初始化消息队列头
    while (a <= m1)
    {
        if (home_arrive[a].time < home_leave[b].time)
        {
            // 到达
            // t=1; // 若强制初始化则超时
            while (home_bdg[t]) //寻找可用廊桥
                t++;
            home_bridge[t]++;                //第t廊桥飞机数+1
            home_bdg[t] = true;              //廊桥被占用
            plane[home_arrive[a].plane] = t; //记录该飞机占用廊桥，以便离开消息处理
            if (t > home)
                home = t; //更新国内廊桥总数
            a++;          // pop home_arrive[a]，下一消息
        }
        else
        {
            // 离开
            t = plane[home_leave[b].plane]; //该飞机占用的廊桥
            home_bdg[t] = false;            //廊桥空闲
            b++;                            // pop home_leave[b]，下一消息
            t = 1;                          //此处需初始化当前廊桥编号，从头遍历寻找可用廊桥
        }
    }
    t = 1;
    // 处理国际飞机
    a = b = 1; //初始化消息队列头
    while (a <= m2)
    {
        if (abroad_arrive[a].time < abroad_leave[b].time)
        {
            // 到达
            // t=1; // 若强制初始化则超时
            while (abroad_bdg[t]) //寻找可用廊桥
                t++;
            abroad_bridge[t]++;                //第t廊桥飞机数+1
            abroad_bdg[t] = true;              //廊桥被占用
            plane[abroad_arrive[a].plane] = t; //记录该飞机占用廊桥，以便离开消息处理
            if (t > abroad)
                abroad = t; //更新国际廊桥总数
            a++;            // pop abroad_arrive[a]，下一消息
        }
        else
        {
            // 离开
            t = plane[abroad_leave[b].plane]; //该飞机占用的廊桥
            abroad_bdg[t] = false;            //廊桥空闲
            b++;                              // pop abroad_leave[b]，下一消息
            t = 1;                            //此处需初始化当前廊桥编号，从头遍历寻找可用廊桥
        }
    }
}
void solve()
{
    int t, ans = 0;              // t为临时变量，ans为答案
    for (int i = 2; i <= n; i++) //小小前缀和
    {
        home_bridge[i] += home_bridge[i - 1];
        abroad_bridge[i] += abroad_bridge[i - 1];
    }
    for (int i = 0; i <= n; i++) //暴力枚举搜索最佳方案
    {
        t = home_bridge[i] + abroad_bridge[n - i];
        if (t > ans)
            ans = t; //更新答案
    }
    cout << ans << endl;
}
int main()
{
    // freopen("airport.in","r",stdin);
    // freopen("airport.out","w",stdout);
    cin >> n >> m1 >> m2; //读入数据头
    read();               //读入数据
    sort(home_arrive + 1, home_arrive + m1 + 1, msgcmp);
    sort(home_leave + 1, home_leave + m1 + 1, msgcmp);
    sort(abroad_arrive + 1, abroad_arrive + m2 + 1, msgcmp);
    sort(abroad_leave + 1, abroad_leave + m2 + 1, msgcmp); //消息数组排序形成队列
    init();                                                //分配
    solve();                                               //枚举方案
    return 0;
}

SuperZDK

楼主是高中么，自己刷题的？

rsjw

ZJ选手初赛前来报到

meguru893

去年打的时候这题才打了25，，，