ACM模版

描述

题解

官方题解：

首先我们需要注意到最重要的一点，所有运输方案同时进行，我们只需要计算最后到达的方案的花费时间的最小值。所以我们需要考虑的是一个极限情况，在这个极限情况下，其他运输方案全部是在允许范围内的。所以我们可以二分枚举这个极限情况，判断所有方案是否都在这个极限内，在的话就继续缩小极限，不在的话就放大极限。至于这个极限呢，涉及到传送门的位置，我们可以将传送门的位置标记为两个区间，初始化这两个区间无限大，然后通过遍历方案来不断压缩这个区间，如果所有的方案都通过后，区间依然是合法的，那么这种极限就是合法的，反之，同理。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
int l[MAXN], r[MAXN];

bool check(int m)
{
    int st_l = -INF, st_r = INF, ed_l = -INF, ed_r = INF;
    for (int i = 1; i <= n; i++)
    {
        if (r[i] - l[i] <= m)
        {
            continue;
        }

        st_l = max(st_l, l[i] + r[i] - m);
        st_r = min(st_r, l[i] + r[i] + m);
        ed_l = max(ed_l, l[i] - r[i] - m);
        ed_r = min(ed_r, l[i] - r[i] + m);
        if (st_l > st_r)
        {
            return 0;
        }
        if (ed_l > ed_r)
        {
            return 0;
        }
    }

    return 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", l + i, r + i);
    }
    for (int i = 1; i <= m; i++)
    {
        if (l[i] > r[i])
        {
            swap(l[i], r[i]);
        }
    }

    int l = 0, r = n, m, ans = -1;
    while (l <= r)
    {
        m = (l + r) >> 1;
        if (check(m))
        {
            ans = m;
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }

    printf("%d\n", ans);

    return 0;
}