[ARC152B] Pass on Path

· · 题解

[ARC152B] Pass on Path

假设两个人分别从 x,y 出发，其中 x<y。显然，他们如果不在同一休息站出发，必定会相遇两次。由于他们速度一样，所以相遇后肯定会反向出发。假设他们在 a 第一次相遇，如果每个位置都有休息站的话，那么他们第二次相遇会在 L-a。事实上并不是每个位置都有休息站，但为了让时间最小，他们会在离 L-a 最近的两个休息站中的一个相遇，把这个休息站记为 b。

考虑两次相遇的间隔为多长。向西走的人需要花费 a-b+2 \times b=a+b 的时间走到西边的尽头并且来到相遇的休息站，向东走的人需要花费 2 \times (L-a)+a-b=2 \times L-a-b 的时间走到东边的尽头并且来到相遇的休息站。间隔时间 T 就是两人要花费的时间取 \max，因为时间短的人要等时间长的人。

如果两个人一开始从同一个休息站反向出发，那么最终花费的时间就是 2 \times T。如果不是从同一个休息站出发的，那么最终花费的时间就是到达第一次相遇的休息站的时间 + 从第二次相遇的休息站回去的时间 +T。如果是同向出发（假设同时向西走），时间为 \max(x+a,y-a)+\max(b-x,2 \times L-y-b)+T。如果是反向出发，时间为 \max(x+a,2 \times L-y-a)+\max(b-x,y-b)+T。可以发现，两个式子中除了 T 以外的部分都不小于 T，因此我们可以证明两个人一开始从同一个休息站反向出发是最优的。

关于代码实现，这里提一个点。我们每次二分找到大于等于 L-a 的第一个 x_i，答案和 \min(a+x_i,2 \times L-a-x_{i-1}) 取 \min。我们之前说 T=\max(a+b,2 \times L-a-b)，但这里为什么不用了呢？因为当 b=L-a 时，两式相等。那么 b 变大，a+b 就一定大于 2 \times L-a-b；b 变小，2 \times L-a-b 一定大于 a+b，所以就省去了取 \max 这一步。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,INF=1e18;
int n,l,ans=INF;
int a[N];
signed main()
{
    scanf("%lld%lld",&n,&l);
    for (int i=1;i<=n;++i) scanf("%lld",&a[i]);
    for (int i=1;i<=n;++i)
    {
        int p=lower_bound(a+1,a+n+1,l-a[i])-a;
        ans=min(ans,min(p<=n?a[i]+a[p]:INF,p>1?l*2-a[i]-a[p-1]:INF));
    }
    printf("%lld\n",ans<<1);
    return 0;
}