题解：P15292 [MCO 2023] Two Pointers (hard version)

lailai0916 · 2026-08-31 01:10:28 · 题解

题意简述

Alice 和 Bob 位于数轴上的不同位置。

现在依次发生 n 个事件，第 i 个事件位于 t_i。每个事件至少需要一人到达对应位置，求两人的最小移动距离之和。

解题思路

处理完第 i 个事件后，一定有人位于 t_i。称其为固定者，只记录另一人的位置 p。

设此时的最小代价为 F_i(p)。处理 t_i 后，移动方式只有以下两种：

• 原固定者从 t_{i-1} 移动到 t_i，另一人仍在 p；
• 原本位于 p 的人移动到 t_i，原固定者留在 t_{i-1}。

第一种方式会让每个已有状态同时增加：

第二种方式只会得到一个另一人位于 t_{i-1} 的新状态，其代价为：

若直接维护 F_i，每次都要给所有状态加上 d_i。因此用 \delta 记录公共增量，并维护：

执行第一种转移时，只需令 \delta\gets\delta+d_i，所有已有的 H(p) 都不变。

考虑如何求第二种转移。令 x=t_i，根据 p 与 x 的大小关系拆开绝对值：

所有可能出现的位置只有 A,B,t_1,\dots,t_n，可以先离散化。在线段树的每个区间分别维护：

这样，一次前缀查询和一次后缀查询即可求出上式。由于同一位置可能多次产生状态，单点修改应对原值取最小值。

设查询结果为 q。加入本轮公共增量后，新状态的归一化代价为：

处理第一个事件时有两种初始状态：

此时 \delta=0。之后依次进行查询、增加 \delta，并插入新状态。答案为最终的 \delta 加所有 H(p) 的最小值。

下面说明状态转移的正确性。

假设处理完事件 i-1 后，所有状态 H(p) 都准确表示另一人位于 p 时的最优代价。处理事件 i 时，若原固定者移动，另一人的位置不变，所有状态恰好统一增加 d_i，由 \delta 完整记录。若另一人移动，其出发位置必为某个 p，移动代价为 |p-t_i|；枚举所有 p 取最小值，便得到另一人留在 t_{i-1} 的唯一新状态。两种情况覆盖了完成事件 i 的全部方式，且都取到了各自的最小代价。因此归纳可知，算法始终维护每个状态的最优代价，最终答案正确。

离散化和每次线段树操作的时间复杂度均为 O(\log n)，故总时间复杂度为 O(n\log n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=300005;
const int M=1048580;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m,s;
ll a,b,t[N],f[M][2];
vector<ll> v;
int get(ll x)
{
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void add(ll x,ll y)
{
    int p=get(x)+s-1;
    f[p][0]=min(f[p][0],y-x);
    f[p][1]=min(f[p][1],y+x);
    for(p>>=1;p;p>>=1)
    {
        f[p][0]=min(f[p*2][0],f[p*2+1][0]);
        f[p][1]=min(f[p*2][1],f[p*2+1][1]);
    }
}
ll ask(int l,int r,int k)
{
    ll res=inf;
    for(l+=s-1,r+=s-1;l<=r;l>>=1,r>>=1)
    {
        if(l&1)res=min(res,f[l++][k]);
        if(!(r&1))res=min(res,f[r--][k]);
    }
    return res;
}
ll query(ll x)
{
    int p=get(x);
    return min(ask(1,p,0)+x,ask(p,m,1)-x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>a>>b;
    v.push_back(a);
    v.push_back(b);
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
        v.push_back(t[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m=v.size();
    for(s=1;s<m;s*=2);
    for(int i=1;i<s*2;i++)
    {
        f[i][0]=inf;
        f[i][1]=inf;
    }
    ll x=abs(a-t[1]);
    add(b,x);
    ll y=abs(b-t[1]);
    add(a,y);
    ll delta=0;
    ll mn=min(x,y);
    for(int i=2;i<=n;i++)
    {
        ll res=query(t[i]);
        ll d=abs(t[i]-t[i-1]);
        delta+=d;
        res-=d;
        add(t[i-1],res);
        mn=min(mn,res);
    }
    cout<<delta+mn<<'\n';
    return 0;
}