基于二分法和动态规划求解一维人群相遇问题
AtCoder 原题大意：
给定 n 个人在数轴上的坐标 a[i]（均为偶数），每个人的最大移动速度为 1。要求每对相邻的人（即第 i 个和第 i+1 个）之间都发生过相遇，求达成该条件所需的最短时间。
数据范围：1 ≤ n ≤ 2×10^5，0 ≤ a[i] ≤ 10^9，坐标严格递增。
解法概述
本解法的时间复杂度为 O(n log n)。
核心思路：对答案时间 t 进行二分查找，并使用动态规划（DP）来验证在给定时间内是否能满足所有相遇条件。
人的两种可能行为
根据最优策略，每个人只有两种行动模式：
- 模式 A：先向右移动与右侧邻居相遇，然后折返向左移动。
- 模式 B：先向左移动与左侧邻居相遇，然后折返向右移动。
动态规划设计
定义二维数组 dp[i][0] 和 dp[i][1]，两值均表示第 i 个人在时间结束时可到达的最右位置坐标（相对于其起始位置）。区别在于：
dp[i][0]：此人采用模式 A（先向右）时，能向右移动的最大额外距离。dp[i][1]：此人采用模式 B（先向左）时，能向右移动的最大额外距离。
对于第一个人，由于没有左侧邻居，两种模式初始值均为 t（全速向右移动获得的最大距离）。
转移策略推导
考虑第 i-1 个人（前驱）与第 i 个人（当前）的行动模式组合。为了可读性，下文用 "前者" 指代第 i-1 人，"后者" 指代第 i 人。
情况 1：前者模式 A + 后者模式 B
前者会先向右移动到达某个点，为保证相遇，后者必须在同一时间点到达该点。因此，前者的可达右边界 a[i-1] + dp[i-1][0] 必须不小于后者能向左到达的最左边界 a[i] - dp[i-1][0]。
if (a[i-1] + dp[i-1][0] >= a[i] - dp[i-1][0]) {
// 条件成立
}
相遇后，后者会折返向右，其可用于向右移动的总时间为 t - (a[i] - a[i-1])，因此转移如下：
dp[i][1] = max(dp[i][1], t - (a[i] - a[i-1]));
情况 2：前者模式 A + 后者模式 A
两人均先向右，初始间距保持不变。一旦前者折返向左，后者将无法追上，因此需要限制在前者折返前能到达的最大位置。
dp[i][0] = max(dp[i][0], dp[i-1][0] - (a[i] - a[i-1]) / 2);
情况 3：前者模式 B + 后者模式 A
前者在 t 秒末的位置为 a[i-1] + dp[i-1][1]。为了保证相遇，后者必须能在 t 秒内到达该点，即 a[i-1] + dp[i-1][1] >= a[i] - t。
if (a[i-1] + dp[i-1][1] >= a[i] - t) {
// 条件成立
}
相遇后，后者向右移动可用的总时间为 t - (a[i] - (a[i-1] + dp[i-1][1]))，由于需要折返，实际向右移动净距离需除以 2：
dp[i][0] = max(dp[i][0], (t - a[i] + a[i-1] + dp[i-1][1]) / 2);
情况 4：前者模式 B + 后者模式 B
两人均先向左移动，相遇后立即一起向右移动。后者的最大向右距离取决于前者的最终位置减去当前间距。
dp[i][1] = max(dp[i][1], dp[i-1][1] + a[i-1] - a[i]);
验证函数实现
二分时通过 check(t) 函数判断 t 时间是否可行。若存在任意一人无法进行合法转移，则 t 不可行。
int dp[MAXN][2];
// dp[i][0]: 先向右的最大右移; dp[i][1]: 先向左的最大右移
void update(int &x, int y) { x = max(x, y); }
bool check(int t) {
for (int i = 2; i <= n; ++i)
dp[i][0] = dp[i][1] = -INF;
dp[1][0] = dp[1][1] = t;
for (int i = 2; i <= n; ++i) {
bool ok = false;
// 情况1+2：前者先右
if (dp[i-1][0] >= (a[i] - a[i-1]) / 2) {
update(dp[i][1], t - (a[i] - a[i-1]));
update(dp[i][0], dp[i-1][0] - (a[i] - a[i-1]) / 2);
ok = true;
}
// 情况3+4：前者先左
if (a[i-1] + dp[i-1][1] >= a[i] - t) {
update(dp[i][0], (t - a[i] + a[i-1] + dp[i-1][1]) / 2);
update(dp[i][1], dp[i-1][1] + a[i-1] - a[i]);
ok = true;
}
if (!ok) return false;
}
return true;
}
主二分流程
二分下限 l = 0，上限 r = (a[n] - a[1]) / 2，并在过程中更新最小可行时间 ans。
int main() {
// 输入处理省略
int ans = (a[n] - a[1]) / 2;
int l = 0, r = (a[n] - a[1]) / 2;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
// 输出 ans
return 0;
}
