[ABC119D] Lazy Faith题解

CCX_CoolMint · 2024-10-16 21:18:23 · 题解

关于这道题，题解区全都是二分的做法，在这里我提供一个不需要二分的方法且非常好理解！

首先我们考虑一个坐标如何达到目标，即前往一家神社和一家寺庙。发现最优情况只有可能是如下四种情况之一：

• 前往该坐标左侧的神社和左侧的寺庙
• 前往该坐标右侧的神社和左侧的寺庙
• 前往该坐标左侧的神社以后，立马折回，向右前往该坐标右侧的寺庙或前往该坐标右侧的寺庙以后，立马折回，向左前往该坐标左侧的神社
• 前往该坐标左侧的寺庙以后，立马折回，向右前往该坐标右侧的神社或前往该坐标右侧的神社以后，立马折回，向左前往该坐标左侧的寺庙

这是显然的。那么对于这四种情况，它们所花费的移动距离是多少？令左侧神社为 Ls，左侧寺庙为 Lt，右侧神社为 Rs，右侧寺庙为 Rt。X 表示一座神社或一座寺庙与该坐标的距离，那么对应的四种情况的移动距离如下：

• max(X_{Ls},X_{Lt})
• max(X_{Rs},X_{Rt})
• min(2X_{Ls}+X_{Rt},2X_{Rt}+X_{Ls})
• min(2X_{Lt}+X_{Rs},2X_{Rs}+X_{Lt})

这样就做完了。时间复杂度瓶颈在排序，为 O(n log n)，其中 n=A+B+Q.

关于具体实现，可以先将所有的坐标（包括神社、寺庙以及询问三种类型的坐标）做上标记（标记他们属于什么类型的坐标），再进行排序。之后对于每一个询问类型的坐标，从前往后、从后往前遍历两遍，找到它们左侧、右侧的神社、寺庙。然后像上面一样计算他们所需要的移动距离，四种情况取最小值即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,q,la,lb,ra,rb,ans;
struct node
{
    ll id,x;
    char op;
}c[1001000];
struct node2
{
    ll la,lb,ra,rb;
}tj[1001000];
bool cmp(node u,node v)
{
    return u.x<v.x;
}
int main()
{
    cin>>a>>b>>q;
    for(int i=1;i<=a;i++) cin>>c[i].x,c[i].op='A';
    for(int i=a+1;i<=a+b;i++) cin>>c[i].x,c[i].op='B';
    for(int i=a+b+1;i<=a+b+q;i++)
    {
        cin>>c[i].x;
        c[i].id=i-a-b;
    }
    sort(c+1,c+1+a+b+q,cmp);
    for(int i=1;i<=a+b+q;i++)
    {
        if(!c[i].id)
        {
            if(c[i].op=='A') la=c[i].x;
            else lb=c[i].x;
        }
        else
        {
            if(la) tj[c[i].id].la=c[i].x-la;
            else tj[c[i].id].la=-1;
            if(lb) tj[c[i].id].lb=c[i].x-lb;
            else tj[c[i].id].lb=-1;
        }
    }
    for(int i=a+b+q;i>=1;i--)
    {
        if(!c[i].id)
        {
            if(c[i].op=='A') ra=c[i].x;
            else rb=c[i].x;
        }
        else
        {
            if(ra) tj[c[i].id].ra=ra-c[i].x;
            else tj[c[i].id].ra=-1;
            if(rb) tj[c[i].id].rb=rb-c[i].x;
            else tj[c[i].id].rb=-1;
        }
    }
    for(int i=1;i<=q;i++)
    {
        ans=LLONG_MAX;
        if(tj[i].la!=-1&&tj[i].lb!=-1) ans=min(ans,max(tj[i].la,tj[i].lb));
        if(tj[i].ra!=-1&&tj[i].rb!=-1) ans=min(ans,max(tj[i].ra,tj[i].rb));
        if(tj[i].la!=-1&&tj[i].rb!=-1) ans=min(ans,min(tj[i].la*2+tj[i].rb,tj[i].rb*2+tj[i].la));
        if(tj[i].ra!=-1&&tj[i].lb!=-1) ans=min(ans,min(tj[i].ra*2+tj[i].lb,tj[i].lb*2+tj[i].ra));
        cout<<ans<<endl;
    }
    return 0;
}