【题解】CF875E：Delivery Club_cf875e题解-CSDN博客

本文链接：https://blog.csdn.net/ModestCoder_/article/details/99320954

本文介绍了一种结合二分答案与贪心策略的算法解决方案，通过具体实例讲解了如何利用这种策略来优化问题求解过程。关键在于根据当前状态贪心地选择最优路径，并通过二分查找确定最合适的参数值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
二分答案+贪心
对于每个 $m i d$ ，需要倒着做，贪心
我们记当前其中一个快递员在 $x_{i+1}$ ，另一个快递员在 $[l, r]$ ，当前那么分类讨论

$x_i在[l,r]中$ ，说明直接走到 $x_i$ 依然满足，可行区间直接变为 $x_i-mid,x_i+mid]$
$x_i不在[l,r]中$ ，说明不动的那个人必须在 $[l, r]$ 中，而且必须满足和 $x_i$ 距离不超过 $m i d$ ，所以可行区间变为 $[l, r]$ 与 $x_i-mid,x_i+mid]$ 的交集

最后判断 $s 1$ 或 $s 2$ 是否在可行区间里即可

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, s1, s2, a[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool check(int mid){
	int l = -1e9, r = 1e9;
	for (int i = n; i; --i)
		if (l <= a[i] && a[i] <= r) l = a[i] - mid, r = a[i] + mid; else
		l = max(l, a[i] - mid), r = min(r, a[i] + mid);
	return (l <= s1 && s1 <= r) || (l <= s2 && s2 <= r);
}

int main(){
	n = read(), s1 = read(), s2 = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	int l = abs(s1 - s2), r = 1e9, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, r = mid - 1; else l = mid + 1;
	}
	printf("%d\n", ans);
	return 0;
}