星际航行（贪心算法，我感觉二分也是可以的，但是没有实现思路）

码题集OJ-星际航行 (matiji.net)

我们分析，怎样移动可以使总体移动距离最少。我们可以考虑一维坐标下，当只有三个飞船的时候我们可以发现只有当两边的飞船向中间的飞船移动移动可以使总体移动距离最少，推广到n个飞船，也是都聚集在中点的坐标可以使移动距离最短。当推广到三维时，我们也可以类别这个思想。在x轴，y轴和z轴排列直线时，那么飞船移动后的其他两个维度必然相等，也就是以各个维度的中间点作为聚集点。剩下的那个以直线排列的维度的坐标就是以大小顺序依次找到自己应该处于的位置即可。

#include
#include
typedef long long LL;
using namespace std;
const int N=1e5+5;
int n;
//sx,sx,sy依次存各个按值排列好的坐标
int sx[N],sy[N],sz[N];
//arr上的各个点到point点的距离之和
LL distToPoint(int arr[],int point) {LL res=0;for(int i=1; i<=n; i++) {res+=abs(arr[i]-point);}return res;
}
//arr上的各个点向中间点靠拢的移动距离之和
LL arrayPoint(int arr[],int point) {LL res=0;//变量t是在当前坐标轴上，排成连续一段的坐标最小值。int t=point-(n-1)/2;for(int i=1; i<=n; i++) {res+=abs(arr[i]-t++);}return res;
}
int main(void) {scanf("%d",&n);for(int i=1; i<=n; i++) {scanf("%d%d%d",&sx[i],&sy[i],&sz[i]);}//将横纵竖坐标分别排序，找出位置处于中间的坐标sort(sx+1,sx+n+1);sort(sy+1,sy+n+1);sort(sz+1,sz+n+1);//dx，dy，dz分别代表每个坐标轴上各个坐标上与中间点的距离之和//需要注意当n为偶数我们取arr[n/2]为中间点，其实arr[n/2]和arr[n/2+1]之间的所有点都是可以的LL dx=distToPoint(sx,sx[n+1>>1]);LL dy=distToPoint(sy,sy[n+1>>1]);LL dz=distToPoint(sz,sz[n+1>>1]);//ax, ay, az分别代表每个坐标轴上的点向中间点靠拢所移动的距离之和LL ax=arrayPoint(sx,sx[n+1>>1]);LL ay=arrayPoint(sy,sy[n+1>>1]);LL az=arrayPoint(sz,sz[n+1>>2]);LL res=min(dx+dy+az,dx+dz+ay);res=min(res,dy+dz+ax);printf("%lld",res);return 0;
}

1. typedef long long LL; 定义一个长整型数据类型LL，它通常用于存储可能比int类型更大的整数。
2. const int N=1e5+5; 定义一个常量N，其值为100005。这个值通常用于定义数组的大小。
3. int sx[N],sy[N],sz[N]; 定义三个数组，分别用于存储x、y、z坐标。
4. distToPoint函数 计算一个数组arr[]中所有点到一个给定点point的距离之和。
5. arrayPoint函数 计算一个数组arr[]中所有点向一个给定点point靠拢所需要的移动距离之和。
6. main函数 首先，读取输入数据，包括坐标的数量和每个坐标的x、y、z值。然后，对x、y、z坐标分别排序。接着，计算每个坐标轴上的点到中间点的距离之和以及每个坐标轴上的点向中间点靠拢所需要的移动距离之和。最后，找出移动距离和最小的排列方式，并打印结果。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！