[CSP-S 2021] 廊桥分配 题解
前言
这道题在考场上我花了足足3个小时，最后线段树上二分的算法写挂了，准备交个暴力，结果因为把国际航班的数量错写为国内航班的数量惨遭爆零，因为这道题，我彻底与1=无缘，为了警醒自己以后不要再犯低级错误，同时看到并没有多少人使用线段树二分做法，我决定写下这篇题解，希望对你也能有所帮助
思路
看了题之后容易想到只需要让每个廊桥上停留的飞机尽量多，分别求出国内航班和国际航班在有 \(n\) 个廊桥时每个廊桥所停留的飞机数，取一个前缀和然后 \(\Theta(n)\) 枚举一遍求 \(\max\) 就能算出答案了
具体地说，先把飞机按照到达顺序排序，对于这 \(n\) 个廊桥中的每一个廊桥我们开一个 \(last\) 数组，其中 \(last_i\) 表示第 \(i\) 个廊桥上最晚离开的飞机离开的时间，对于每一架飞机，我们需要找到满足 \(last_i\) 小于飞机的着陆时间且 \(i\) 尽可能小的廊桥，将这个廊桥的停留飞机数加上一并把它的 \(last_i\) 更新为这架飞机的离开时间即可，找不到这样的廊桥就说明不得不新使用一个未使用的廊桥，把廊桥总数加一并更新
那么问题（复杂度）的关键就来到了如何快速找到满足 \(last_i\) 小于飞机的着陆时间且 \(i\) 尽可能小的廊桥
暴力
分析
很容易想到暴力从小到大枚举廊桥，找到的满足 \(last_i\) 小于飞机的着陆时间的第一个廊桥就是问题的解，找不到这样的廊桥就说明不得不新使用一个未使用的廊桥
复杂度：\(\Theta(n(m_1+m_2))\)
期望得分：\(40\) 到 \(60\) （然而某谷的屑数据可以直接100）
c++ code
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 2100000000
#define in read()
using namespace std;
struct Plane
{
int ar,le;//到达时间，离开时间
}pl[MAXN];
int lst[MAXN],layer,num[MAXN],tot[MAXN][2];//last数组，已使用廊桥数，廊桥容纳飞机数，前缀和求答案数组
int n,m1,m2;//如题意
inline bool cmp(Plane x,Plane y){return x.ar<y.ar;}//排序
inline int read()//IO优化
{
int x=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
void mwrite(int x)
{
if(x>9)mwrite(x/10);
putchar((x%10)|48);
}
void write(int x,char c)
{
mwrite(x<0?(putchar('-'),-x):x);
putchar(c);
}
signed main()
{
freopen("airport.in","r",stdin);
freopen("airport.out","w",stdout);
n=in,m1=in,m2=in;
//先处理国内航班，然后处理国际航班，前后无太大差异
for(int i=1;i<=m1;++i) pl[i].ar=in,pl[i].le=in;
sort(pl+1,pl+m1+1,cmp);//排序
for(int i=1,tmp;i<=m1;++i)
{
tmp=0;
for(int j=1;j<=layer;++j)
if(pl[i].ar>lst[j])//暴力枚举所有廊桥，找到满足的就退出
{
tmp=j;
break;
}
if(!tmp) lst[++layer]=pl[i].le,++num[layer];//没找到就新加一层
else lst[tmp]=pl[i].le,++num[tmp];//找到了就更新信息
}
for(int i=1;i<=n;++i) tot[i][0]=num[i]+tot[i-1][0];//求前缀和
layer=0;
memset(num,0,sizeof(num));//一定要记得初始化
for(int i=1;i<=m2;++i) pl[i].ar=in,pl[i].le=in;
sort(pl+1,pl+m2+1,cmp);
for(int i=1,tmp;i<=m2;++i)
{
tmp=0;
for(int j=1;j<=layer;++j)
if(pl[i].ar>lst[j])
{
tmp=j;
break;
}
if(!tmp) lst[++layer]=pl[i].le,++num[layer];
else lst[tmp]=pl[i].le,++num[tmp];
}
for(int i=1;i<=n;++i) tot[i][1]=num[i]+tot[i-1][1];
int ans=-1;
for(int i=0;i<=n;++i)ans=max(ans,tot[i][0]+tot[n-i][1]);//枚举一遍所有可能求最大值
write(ans,'\n');
return 0;
}
正解
分析
想要优化复杂度，只能在寻找满足要求的廊桥上下功夫，可以尝试使用数据结构优化
假设第 \(i\) 架飞机于 \(ar_i\) 到达，那么显然当且仅当 \(last\) 的最小值小于 \(ar_i\) 时才能继续使用已经用过的廊桥，那么我们在暴力中枚举编号最小的满足条件的廊桥就可以换一种看法，变成“我们需要从 \(1\) 开始不断扩大 \(j\) 直到编号为 \(1\) 到 \(j\) 的廊桥中 \(last\) 的最小值小于 \(ar_i\)”
也就是说我们要找到这样一个 \(i\)，使得 \(last_1\) 到 \(last_{i-1}\) 的最小值大于 \(ar_j\) 且 \(last_{1}\) 到 \(last_{i}\) 的最小值小于 \(ar_j\)
这样的 \(i\) 显然只有一个，那么容易想到用线段树来维护区间最小值，然后在 \(last_{1}\) 到 \(last_{layer}\) 二分查找对应的 \(i\)，如果最小值小于 \(ar_j\) 就去前半段继续找，否则就去后半段找
对于每一架飞机需要二分找一遍，每一次查询最小值复杂度 \(\Theta(\log_2n)\)，二分法最坏情况查询 \(\Theta(\log_2n)\) 次，也就是说对于每架飞机需要 \(\Theta(\log^2_2n)\) 来处理
复杂度：\(\Theta((m_1+m_2)\log^2_2n)\)
期望得分：100
c++ code
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 2100000000
#define in read()
using namespace std;
struct Plane
{
int ar,le;//到达时间，离开时间
}pl[MAXN];
struct Seg//线段树板子
{
struct Node
{
int ls,rs,v;//维护最小值
}node[MAXN<<2];
void build(int l,int r,int pos)//建树
{
node[pos].ls=l,node[pos].rs=r,node[pos].v=0;//最开始last值都为0
if(l==r)return;
int mid=(l+r)>>1;
build(l,mid,pos<<1);
build(mid+1,r,(pos<<1)+1);
}
void change(int x,int v,int pos)//单点修改
{
if(node[pos].ls==node[pos].rs)
{
node[pos].v=v;
return;
}
int mid=(node[pos].ls+node[pos].rs)>>1;
if(x<=mid)change(x,v,pos<<1);
else change(x,v,(pos<<1)+1);
node[pos].v=min(node[pos<<1].v,node[(pos<<1)+1].v);
}
int ask(int l,int r,int pos)//区间查询最小值
{
if(l<=node[pos].ls&&node[pos].rs<=r) return node[pos].v;
int ans=INF,mid=(node[pos].ls+node[pos].rs)>>1;
if(l<=mid) ans=min(ans,ask(l,r,pos<<1));
if(r>mid) ans=min(ans,ask(l,r,(pos<<1)+1));
return ans;
}
}lst;
int layer,num[MAXN],tot[MAXN][2];//已使用廊桥，廊桥容纳飞机数，前缀和统计答案
int n,m1,m2;//如题意
inline bool cmp(Plane x,Plane y){return x.ar<y.ar;}
inline int read()//IO优化
{
int x=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
void mwrite(int x)
{
if(x>9)mwrite(x/10);
putchar((x%10)|48);
}
void write(int x,char c)
{
mwrite(x<0?(putchar('-'),-x):x);
putchar(c);
}
signed main()
{
freopen("airport.in","r",stdin);
freopen("airport.out","w",stdout);
n=in,m1=in,m2=in;
//先处理国内航班
for(int i=1;i<=m1;++i) pl[i].ar=in,pl[i].le=in;
sort(pl+1,pl+m1+1,cmp);//按到达时间排序
lst.build(1,m1,1);//建树
for(int i=1,ll,rr,mm;i<=m1;++i)//枚举飞机
{
ll=0,rr=layer;//二分
while(ll<rr)
{
mm=(ll+rr)>>1;
if(pl[i].ar>lst.ask(1,mm,1)) rr=mm;//满足就继续找更小的
else ll=mm+1;//不满足就继续找更大的
}
if(ll==layer)//如果找到最后一个那么可能是无解，需要使用新廊桥
if(pl[i].ar<lst.ask(1,ll,1))
ll=0;
if(!ll) lst.change(++layer,pl[i].le,1),++num[layer];//不行就使用新的廊桥
else lst.change(ll,pl[i].le,1),++num[ll];//可行就更新廊桥信息
}
for(int i=1;i<=n;++i) tot[i][0]=num[i]+tot[i-1][0];//前缀和统计答案
//国际航班
layer=0;
memset(num,0,sizeof(num));//记得初始化
for(int i=1;i<=m2;++i) pl[i].ar=in,pl[i].le=in;
sort(pl+1,pl+m2+1,cmp);
lst.build(1,m2,1);
for(int i=1,ll,rr,mm,tmp;i<=m2;++i)
{
ll=0,rr=layer;
while(ll<rr)
{
mm=(ll+rr)>>1;
if(pl[i].ar>lst.ask(1,mm,1)) rr=mm;
else ll=mm+1;
}
if(ll==layer)
if(pl[i].ar<lst.ask(1,ll,1))
ll=0;
if(!ll) lst.change(++layer,pl[i].le,1),++num[layer];
else lst.change(ll,pl[i].le,1),++num[ll];
}
for(int i=1;i<=n;++i) tot[i][1]=num[i]+tot[i-1][1];
int ans=-1;
for(int i=0;i<=n;++i)ans=max(ans,tot[i][0]+tot[n-i][1]);//遍历枚举答案
write(ans,'\n');
return 0;
}
该文为本人原创，转载请注明出处