题目描述

Daniel 正在玩一个战棋游戏。
现在Daniel 有n 队士兵站在x 轴上。第i 队士兵有ai 人，坐标为xi。
Daniel 看到一队士兵有这么多人，都站在同一个位置，他对此很不满意。他
想命令一些士兵移动到新的位置（必须是整点），使得不存在两个士兵站在同一个
位置。
为了节约时间，Daniel 希望每个士兵的移动距离的最大值尽可能小。请求出这个最小值。

思路

用jp的话来说 ，求最大的最小值很有可能是二分答案
二分一个数m，显然每一队士兵可以走[x-t,x+t]这个区间，那么设从最左边开始走，走到最右边就是 l+a[i], 如果这个值>x+t 那说明这个答案是不行的，继续二分，如果可行，那下一队士兵的开始点就为max(l+a[i],x-t)

#include <stdio.h>
#define maxn 100001
#define INF 0x7f7f7f7f
int a[maxn], b[maxn];
int n;
int chack(int t)
{
    int l = -INF;
    for (int i = 1; i <= n; i++)
    {
        int xl = b[i] - t, xr = b[i] + t;
        if (l < xl) l = xl;
        if (l + a[i] - 1 > xr) return 0;
        l += a[i];
    }
    return 1;
}
int main()
{
    freopen("distinct.in", "r", stdin);
    freopen("distinct.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    int l = -1, r = INF;
    while (l + 1 < r)
    {
        int m = (l + r) >> 1;
        int xx = chack(m);
        if (xx == 1) r = m;
        else l = m;
    }
    printf("%d\n", r);
}