ARC152B. Pass on Path题解

发表于 分类于

题目传送门

题意：有一个 [0,L][0,L] 的数轴，分布有 nn 个休息站，每个休息站坐标为 aia_i。A、B 两人速度均为 11，他们分别从某个休息站开始，向某个方向走，每人都遍历完两个端点后回到原地。两人只有在休息站才能交错，而不能在路上穿过。求最小时间。

首先发现一个性质：AB 一定会交错两次，总时间即为 2L+max⁡(waitA,waitB)2L+\max(wait_A,wait_B)，其中 waitA,waitBwait_A,wait_B 分别表示 AB 等待的时间。由于前者为定值，所以可以推出一个结论为，AB 的起点一定相同。于是对于每个起点，我们只需要找出 AB 两人等待时间最短的“第二次交错位置”即可。由于等待的时间即为 AB 路径长度的差，所以一定要求最接近，可以使用双指针或 lower_bound 计算。

By Um_nik

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
28
29
const ll INF = (ll)1e12;
const int N = 500500;
int n;
ll L;
ll a[N];
ll ans = INF;

int main()
{
    startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

    scanf("%d%lld", &n, &L);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n);
    int p = 0, q = n - 1;
    while(p < n && q >= 0) {
        ans = min(ans, abs(a[p] + a[q] - L));
        if (a[p] + a[q] >= L)
            q--;
        else
            p++;
    }
    printf("%lld\n", 2 * L + 2 * ans);

    return 0;
}