题目描述

难度分:$1400$

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

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

一条街道上有$n$个工厂，第$i$个工厂的位置是$a[i]$。你需要建造$3$个仓库，仓库的位置由你决定，必须是整数。每个工厂生产的物品要运到离其最近的仓库。

定义$d(i)=$第$i$个工厂到离其最近的仓库的距离。设$M=$所有$d(i)$的最大值。最小化$M$，也就是最小化最大的工厂到仓库的距离。

输入样例

5
6
1 7 7 9 9 9
6
5 4 2 1 30 60
9
14 19 37 59 1 4 4 98 73
1
2
6
3 10 1 17 15 11

输出样例

0
2
13
0
1

算法

前后缀分解+二分答案

这个题才$1400$，真的感觉不太容易。这种“三元组”类的题目比较容易想到的思路就是前后缀分解，先将$a$数组排序，枚举最左边仓库管辖的最右边的工厂$i$，根据中位数贪心的结论，此时最左侧仓库的位置就应该是$pos=\lfloor \frac{a[1]+a[i]}{2} \rfloor$，其中$\lfloor . \rfloor$表示对$.$向下取整，工厂$[1,i]$到这个仓库距离的最大值就应该是$a[i]-mid$。枚举最右边仓库管辖的最左边工厂$i$，同理，最右侧仓库的位置就应该是$pos=\lfloor \frac{a[n]+a[i]}{2} \rfloor$，预处理出$pre$和$suf$两个数组，其中$pre[i]=a[i]-\lfloor \frac{a[1]+a[i]}{2} \rfloor$，$suf[i]=a[n]-\lfloor \frac{a[n]+a[i]}{2} \rfloor$。

接下来根据题面的关键词求最大值的最小值，可以尝试二分这个答案。对于一个给定的最大距离限制$limit$，分为以下两种情况：

1. 如果所有工厂到$3$个仓库的距离不超过$limit$，那么这个$limit$可能是答案，记录一下并向左搜索看能不能更小。
2. 如果所有工厂到$3$个仓库的距离一定大于$limit$，说明$limit$太小了，往右搜索。

关键还是在于怎么检查这个$limit$是否满足要求，我们可以遍历中间仓库管辖的最左边工厂$i \in [2,n)$，这时最左边的仓库管辖的工厂范围就是$[1,i-1]$，这些工厂到最左边仓库的最大距离就是$pre[i-1]$，首先要满足的就是$pre[i-1] \leq limit$，满足这个条件的时候再考虑中间仓库的管辖范围。接下来要确定中间仓库管辖工厂的右边界，由于最大距离不能超过$limit$，所以这个工厂的位置距离$a[i]$不能超过$a[i]+2limit$，二分一下就能找到这个$j$。此时，最右边仓库的管辖范围左边界可以在区间$k \in [i+1,j+1]$，只要这个区间内的$suf[k]$最小值不超过$limit$，就找到了三段符合要求的区间，$limit$是合法的。

注意到这里还存在一个查询区间最小值的操作，即查询$suf$在$[i+1,j+1]$内的最小值，所以用倍增做个预处理就行。

复杂度分析

时间复杂度

预处理出$pre$和$suf$需要对$a$排序，接下来是线性复杂度，所以时间复杂度为$O(nlog_2n)$。预处理出$suf$的$ST$表时间复杂度也是$O(nlog_2n)$。最后是二分答案，设值域跨度为$A$，$check$函数要遍历$i \in [1,n)$，对于每个$i$，要二分得到$j$，然后$O(1)$查询$[i+1,j+1]$内$suf$的最小值，$check$的时间复杂度也为$O(nlog_2n)$。

综上，整个算法的时间复杂度在于后面的二分答案，为$O(log_2Anlog_2n)$。

空间复杂度

空间瓶颈在于$suf$数组的$ST$表，$pre$数组和$suf$数组都是线性的。因此，算法的额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010, M = 20, INF = 1e9;
int n, a[N];

int main() {
    int T;
    scanf("%d", &T);
    for(int cases = 1; cases <= T; cases++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1);
        n = unique(a + 1, a + n + 1) - a - 1;
        int pre[n + 1], suf[n + 1], st[n + 1][M];
        for(int i = 1; i <= n; i++) {
            pre[i] = a[i] - (a[1] + a[i])/2;
        }
        for(int i = n; i >= 1; i--) {
            suf[i] = a[n] - (a[i] + a[n])/2;
        }
        for(int j = 0; j < M; j++) {
            for(int i = 1; i + (1 << j) - 1 <= n; i++) {
                if(j == 0) {
                    st[i][j] = suf[i];
                }else {
                    st[i][j] = min(st[i][j - 1], st[i + (1<<(j - 1))][j - 1]);
                }
            }
        }
        function<int(int, int)> query = [&](int l, int r) {
            int k = log2(r - l + 1);
            return min(st[l][k], st[r - (1<<k) + 1][k]);
        };
        function<bool(int)> check = [&](int limit) {
            for(int i = 2; i < n; i++) {
                if(pre[i - 1] <= limit) {
                    int j = upper_bound(a + 1, a + n + 1, a[i] + 2LL*limit) - a;
                    --j;
                    // [i+1,j+1]中是否存在suf[k]<=limit的k
                    if(query(i + 1, j + 1) <= limit) {
                        return true;
                    }
                }
            }
            return false;
        };
        int l = 0, r = 1e9;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(mid)) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        printf("%d\n", n <= 3? 0: r);
    }
    return 0;
}