CSP-S 2021 T1 廊桥分配 (airport) 的另一种解法
// 新人第一次发帖 // 本帖首发于申请专区，因为难度系数太低所以未通过，今年暑假开放注册时才注册成功（555），仅提供一种思路（也是做个回忆） 闲话不多说，进入正文：洛谷上的题解大多是优先队列、线段树、pair等， 这里提供一种“无脑运算”的解法 比赛时首先想的想到的是模拟，但超时。 在模拟时发现“新加入廊桥可以视为原先的远机位的一部分”的重要结论，所以将远机位视为廊桥进行预处理，再枚举搜索最佳方案，得到结果。 预处理部分运用仿Windows消息处理的机制（个人认为既然是操作系统都在用的方法，一定很优秀） 上代码：（图片就免了~） /*
Score100 AC
Memory 3.5 M/ 256M
Time 220 ms / 1000 ms
采用非传统方法
灵感来自Windows的消息处理队列机制
预备结论：新加入廊桥可以视为原先的远机位的一部分
*/
#include <bits/stdc++.h>
using namespace std;
struct message
{
int time;
int plane;
}; //定义结构体——消息
message home_arrive,home_leave;
message abroad_arrive,abroad_leave; //消息队列数组
int n, m1, m2;
int home, abroad; //国内国际廊桥总数
int home_bridge, abroad_bridge;//国内国际廊桥的飞机数
int plane; //飞机使用的廊桥
bool home_bdg, abroad_bdg; //国内国际廊桥是否被占用
void read() //输入
{
for (int i = 1; i <= m1; i++)
{
home_arrive.plane = home_leave.plane = i; //飞机编号
scanf("%d %d", &home_arrive.time, &home_leave.time); //输入
}
for (int i = 1; i <= m2; i++)
{
abroad_arrive.plane = abroad_leave.plane = i; //飞机编号
scanf("%d %d", &abroad_arrive.time, &abroad_leave.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.time < home_leave.time)
{
// 到达
// t=1; // 若强制初始化则超时
while (home_bdg) //寻找可用廊桥
t++;
home_bridge++; //第t廊桥飞机数+1
home_bdg = true; //廊桥被占用
plane.plane] = t; //记录该飞机占用廊桥，以便离开消息处理
if (t > home)
home = t; //更新国内廊桥总数
a++; // pop home_arrive，下一消息
}
else
{
// 离开
t = plane.plane]; //该飞机占用的廊桥
home_bdg = false; //廊桥空闲
b++; // pop home_leave，下一消息
t = 1; //此处需初始化当前廊桥编号，从头遍历寻找可用廊桥
}
}
t = 1;
// 处理国际飞机
a = b = 1; //初始化消息队列头
while (a <= m2)
{
if (abroad_arrive.time < abroad_leave.time)
{
// 到达
// t=1; // 若强制初始化则超时
while (abroad_bdg) //寻找可用廊桥
t++;
abroad_bridge++; //第t廊桥飞机数+1
abroad_bdg = true; //廊桥被占用
plane.plane] = t; //记录该飞机占用廊桥，以便离开消息处理
if (t > abroad)
abroad = t; //更新国际廊桥总数
a++; // pop abroad_arrive，下一消息
}
else
{
// 离开
t = plane.plane]; //该飞机占用的廊桥
abroad_bdg = false; //廊桥空闲
b++; // pop abroad_leave，下一消息
t = 1; //此处需初始化当前廊桥编号，从头遍历寻找可用廊桥
}
}
}
void solve()
{
int t, ans = 0; // t为临时变量，ans为答案
for (int i = 2; i <= n; i++) //小小前缀和
{
home_bridge += home_bridge;
abroad_bridge += abroad_bridge;
}
for (int i = 0; i <= n; i++) //暴力枚举搜索最佳方案
{
t = home_bridge + abroad_bridge;
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;
} 楼主是高中么，自己刷题的？ ZJ选手初赛前来报到 去年打的时候这题才打了25，，，
页:
[1]