题目描述

难度分:$1600$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$x(0 \leq x[i] \leq 10^8)$和长为$n$的数组$t(0 \leq t[i] \leq 10^8)$。

你需要计算一个$x_0$，使得$t[i] + |x[i]-x_0|$的最大值最小，输出$x_0$，$x_0$可以是浮点数。

输入样例

7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6

输出样例

0
2
2.5
2
1
3
6

算法

二分答案

这个题要把最大值最小化，很容易想到二分答案，而$x_0$还可以是浮点数，所以自然而然的想到实数二分。对于一个给定的$limit$，要想对于任何$i \in [1,n]$都满足$t[i]+|x[i]-x_0| \leq limit$，需要求出所有不等式解集的交集。将绝对值符号拆开，得到每个不等式的解集为$[x[i]+t[i]-limit,x[i]-t[i]+limit]$，且$t[i] \leq limit$必须成立，$O(n)$求每个不等式解集的交集。

1. 如果这个交集不为空，说明有解。直接把交集$[left,right]$的左端点$left$赋值给$x_0$，并往左搜索$limit$看这个最大值能不能更小。
2. 否则无解，放宽最大值的限制，往右搜索$limit$。

由于实数二分有可能一直达不到精度要求，因此我加了个最多迭代$100$次的限制。

复杂度分析

时间复杂度

实数二分的二分次数为$max(100,log_2A)$，每次$check$的时间复杂度为$O(n)$，因此总的时间复杂度为$O(max(100,log_2A)n)$。

空间复杂度

求解过程中仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;
const double eps = 1e-8;
int t, n, a[N], b[N];
double x0;

bool check(double limit) {
    double left = -1e9, right = 1e9;
    for(int i = 1; i <= n; i++) {
        if(b[i] <= limit) {
            left = max(left, a[i] + b[i] - limit);
            right = min(right, a[i] - b[i] + limit);
        }else {
            return false;
        }
    }
    if(left <= right) {
        x0 = left;
        return true;
    }else {
        return false;
    }
}

void solve() {
    double l = 0, r = 1e9;
    for(int i = 0; i < 100 && r - l > eps; i++) {
        double mid = (l + r)*0.5;
        if(check(mid)) {
            r = mid;
        }else {
            l = mid;
        }
    }
    printf("%.8lf\n", x0);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        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]);
        }
        solve();
    }
    return 0;
}