ARC152B 题解

发表于 更新于
未能场切的简单题

题意简述

在一条细长的路上有若干个休息区，有两个人在走路。每个人都需要从某一休息区出发，到达路的两个端点并返回初始休息区。由于路很狭窄，两人只能在休息区相遇，也就是说某人可能需要在某一休息区等另外一个人。请你做出合适的安排使得从两人出发到两人都回到出发点的总时间最少。

思路分析

约定：令 \(x,y\) 分别表示两人的出发点，钦定 \(x<y\)；令 \(t,w\) 分别表示两次的相遇点。

阅读题目后，不难发现，除非两人从同一点出发，否则他们一定会相遇两次。

由于两人必须在等候区相遇，我们容易发现两人在第一次相遇后会同时同地反向出发。

由此，我们可以容易地找到他们第二次相遇的等候区。设第一次在 \(t\) 相遇，则第二次在离 \(l-t\) 最近两个等候区之一相遇。

我们令 \(S\) 表示两次相遇之间经过的时间，则有 \(S=\max(t+w,2l-t-w)\)，这个式子的两部分分别表示到达左边的端点并折返与到达右边的端点并折返。

如果两人从同一端点出发，则答案就为 \(2S\)，原因显然。

否则答案为 \(\text{第一次相遇的时间}+\text{第二次相遇后回出发点的时间}+S\)。

下面我们来研究这个第一次相遇的时间。

  • 同向出发： \[ ans=\max(t+x,y-t)+\max(w-x,2l-w-y)+S \]

  • 反向出发： \[ ans=max(x+t,2l-t-y)+max(w-x,y-w)+S \]

我们发现，无论是哪一种情况，这个 \(ans\) 的左边部分都一定不小于 \(S\)，因为 \(S\) 中的两种情况在 \(ans\) 中都有出现。因此，我们证明了两人从同一端点出发一定能获得最优解。

以上过程明晰了过后，代码也就很简单了（鸣谢 @Sukwants @ Song_gch 两位大佬的思路和代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 2e5;

int N;
long long L, a[MAXN + 5];
long long Ans = 0x3f3f3f3f3f3f3f3f;

int main()
{
    scanf("%d%lld", &N, &L);
    for (int i = 1; i <= N; ++i) scanf("%lld", a + i);

    for (int i = 1; i <= N; ++i)
    {
        int x = lower_bound(a + 1, a + N + 1, L - a[i]) - a;
        Ans = min(Ans, min(x <= N ? (a[i] + a[x]) : 0x3f3f3f3f3f3f3f3f, x > 1 ? ((L << 1) - a[i] - a[x - 1]) : 0x3f3f3f3f3f3f3f3f));
    }

    printf("%lld\n", Ans << 1);

    return 0;
}