题解：CF2185E The Robotic Rush

· · 题解

前言

一眼看上去以为是整体二分。

但是发现是糖糖题。

Description

在一条无限长的数轴上，有 n 个机器人和 m 个尖刺，每个都位于数轴的某个特定位置。第 i 个机器人位于位置 a_i，第 i 个尖刺位于位置 b_i。如果一个机器人碰到一个尖刺，它就会死亡。

共有 k 条指令被传达给机器人，每条指令要么是向左移动一单位，要么是向右移动一单位。

对于每个 i（1 \leq i \leq k），输出在前 i 条指令执行后，仍然存活的机器人数量。

Solution

对每个机器人处理出来向左向右走多少距离会碰到尖刺。

发现对于一个机器人一定是一个时刻之前存活，一个时刻后死亡。

因此可以对于每个 1\le i\le k 都记录 [1,i] 的操作中，向左走的最长距离，向右走的最长距离。

如果走的最远距离对于这个机器人碰到了尖刺，那这个机器人在这个时刻就是死亡的。

所以可以二分。

时间复杂度 O(n\log n+n\log k)。

Code

:::info[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

int n,m,k;
int a[200010],b[200010];

int opt[200010];
int pos[200010],hisL[200010],hisR[200010];

int Ans[200010];

int main(){
    cin.tie(0)->sync_with_stdio(false);

    int T;cin>>T;
    while(T--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i];
        sort(a+1,a+1+n);
        sort(b+1,b+1+m);

        for(int i=1;i<=k;i++){
            char c;cin>>c;
            if(c=='L') opt[i]=-1;
            else opt[i]=1;
        }

        for(int i=1;i<=k;i++){
            pos[i]=pos[i-1]+opt[i];
            hisL[i]=min(hisL[i-1],pos[i]);
            hisR[i]=max(hisR[i-1],pos[i]);
        }

        b[0]=-inf;
        b[m+1]=inf;

        Ans[0]=n;
        for(int i=1;i<=k;i++) Ans[i]=0;

        for(int i=1;i<=n;i++){
            int dtl=0,dtr=0;
            if(1){
                int l=0,r=m;
                while(l<r){
                    int mid=(l+r+1)>>1;
                    if(b[mid]<a[i]) l=mid;
                    else r=mid-1;
                }
                dtl=b[l]-a[i];
                dtr=b[l+1]-a[i];
            }

            if(1){
                int l=1,r=k+1;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(hisL[mid]<=dtl||hisR[mid]>=dtr) r=mid;
                    else l=mid+1;
                }
                Ans[l]--;
            }
        }

        for(int i=1;i<=k;i++) Ans[i]+=Ans[i-1];
        for(int i=1;i<=k;i++) cout<<Ans[i]<<" ";
        cout<<"\n";
    }

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::