[hdu7032]Command and Conquer: Red Alert 2

令$(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(n\log 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\n",(ans+1>>1));

39     }

40     return 0;

41 }

巴特西

[hdu7032]Command and Conquer: Red Alert 2

最新文章

热门文章