首先我们可以把攻击范围改成 $x \in [x_0,x_0 + 2k], y \in [y_0,y_0 + 2k], z \in [z_0,z_0 + 2k]$。

这显然是对的，这样攻击范围下的决策移动 $(-k,-k,-k)$ 就是原攻击范围下的决策。

首先我们对 $x$，$y$，$z$ 分别排序。

我们取出 $x$，$y$，$z$ 的最小元素 $i$，$j$，$k$。

我们可以先移动到 $(x_i,y_j,z_k)$，这时我们需要射击 $i$，$j$，$k$ 中的一个。

显然我们可以射击需求距离最小的那一个，然后删掉它。

这为什么是对的呢？

我们不妨设这是 $i$，那么我们删掉 $i$，找到 $i’$。

那么我们移动到了 $(x_{i’},y_j,z_k)$。

显然 $x_i \leq x_{i’}$。

故 $j$，$k$ 的射击需求距离变小，所以每次选最小的操作是对的。

然后我们取出新的 $i$，$j$，$k$ 继续做即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
#define fir first
#define sec second
const int maxn=5e5;
int n,K;
int a[maxn+5],b[maxn+5],c[maxn+5];
P va[maxn+5],vb[maxn+5],vc[maxn+5];
bool vis[maxn+5];
inline int Calc(int pa,int pb,int pc,int ta,int tb,int tc){
    return max({ta-pa,tb-pb,tc-pc});
}
signed main(){
    // freopen("hunt.in","r",stdin);
    // freopen("hunt2.in","r",stdin);
    // freopen("hunt.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        va[i]=P(a[i],i);
        vb[i]=P(b[i],i);
        vc[i]=P(c[i],i);
    }
    a[n+1]=b[n+1]=c[n+1]=1e9+7;
    va[n+1]=vb[n+1]=vc[n+1]=P(1e9+7,n+1);
    sort(va+1,va+n+1);
    sort(vb+1,vb+n+1);
    sort(vc+1,vc+n+1);
    for(int i=1,j=1,k=1;i<=n||j<=n||k<=n;){
        while(vis[va[i].sec]) i++;
        while(vis[vb[j].sec]) j++;
        while(vis[vc[k].sec]) k++;
        int ti=Calc(va[i].fir,vb[j].fir,vc[k].fir
            ,a[va[i].sec],b[va[i].sec],c[va[i].sec]);
        int tj=Calc(va[i].fir,vb[j].fir,vc[k].fir
            ,a[vb[j].sec],b[vb[j].sec],c[vb[j].sec]);
        int tk=Calc(va[i].fir,vb[j].fir,vc[k].fir
            ,a[vc[k].sec],b[vc[k].sec],c[vc[k].sec]);
        int tt=min({ti,tj,tk});
        K=max(K,tt);
        if(ti==tt) vis[va[i].sec]=1;
        else if(tj==tt) vis[vb[j].sec]=1;
        else vis[vc[k].sec]=1;
    }
    printf("%d",(int)ceil(K/2.0));
    return 0;
}