ACM模版
描述
题解
官方题解：
首先我们需要注意到最重要的一点，所有运输方案同时进行，我们只需要计算最后到达的方案的花费时间的最小值。所以我们需要考虑的是一个极限情况，在这个极限情况下，其他运输方案全部是在允许范围内的。所以我们可以二分枚举这个极限情况，判断所有方案是否都在这个极限内，在的话就继续缩小极限，不在的话就放大极限。至于这个极限呢，涉及到传送门的位置，我们可以将传送门的位置标记为两个区间，初始化这两个区间无限大，然后通过遍历方案来不断压缩这个区间，如果所有的方案都通过后，区间依然是合法的，那么这种极限就是合法的，反之，同理。
代码
代码语言：javascript复制#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("%dn", ans);
return 0;
}
