令$(x,y,z)$为狙击手的坐标,其攻击范围即以$(x,y,z)$为中心的$(2k)^{3}$的立方体
为了避免$k$的影响(二分答案会多一个$log$),不妨将其变为以$(x,y,z)$为左下角的$(2k)^{3}$的立方体,注意到这样仅仅是实现了平移,并不影响答案
由此,注意到任意时刻,$x,y$和$z$都不应小于剩余点中对应维坐标的最小值,同时若不是最小值调整为最小值显然也不劣,因此不妨假设都恰为最小值
进一步的,显然最终的$k$必然要能消灭其中一个敌人,否则无法移动,那么也就永远不能消灭这些敌人,因此不妨将答案对最小的$k$(能攻击到其中一个敌人)取$max$,并消灭对应的敌人
关于这个过程,可以用三个set来维护,并且每一次至少消灭一个敌人,即至多$o(n)$次
总复杂度为$o(nlog n)$,可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 struct Data{ 5 int x,y,z; 6 }a[N]; 7 set<pair<int,int> >Sx,Sy,Sz; 8 int t,n,ans; 9 int dis(Data x,Data y){ 10 return max(max(x.x-y.x,x.y-y.y),x.z-y.z); 11 } 12 void del(int k){ 13 Sx.erase(make_pair(a[k].x,k)); 14 Sy.erase(make_pair(a[k].y,k)); 15 Sz.erase(make_pair(a[k].z,k)); 16 } 17 int main(){ 18 scanf("%d",&t); 19 while (t--){ 20 scanf("%d",&n); 21 ans=0,Sx.clear(),Sy.clear(),Sz.clear(); 22 for(int i=1;i<=n;i++){ 23 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); 24 Sx.insert(make_pair(a[i].x,i)); 25 Sy.insert(make_pair(a[i].y,i)); 26 Sz.insert(make_pair(a[i].z,i)); 27 } 28 while (!Sx.empty()){ 29 int x=(*Sx.begin()).second; 30 int y=(*Sy.begin()).second; 31 int z=(*Sz.begin()).second; 32 Data o=Data{a[x].x,a[y].y,a[z].z}; 33 ans=max(ans,min(min(dis(a[x],o),dis(a[y],o)),dis(a[z],o))); 34 if (dis(a[x],o)<=ans)del(x); 35 if (dis(a[y],o)<=ans)del(y); 36 if (dis(a[z],o)<=ans)del(z); 37 } 38 printf("%d ",(ans+1>>1)); 39 } 40 return 0; 41 }
View Code