AcWing 104. 货仓选址(Java解法^ ^)
原题链接
简单
作者:
是晴天呀
,
2021-01-31 17:26:18
,
所有人可见
,
阅读 435
/**感觉有点像初二的数学题,记得呢时候好像有一章全是最短路径问题?
先在一维数轴上画两个点A、B,你会发现到AB距离最短的点总是在两点之间的线段上
依次画四个点ABCD也一样,目标点首先在AD之间,之后又在BC之间
所以直接将数轴上的点排好序之后一前一后对应相减即可
所有偶数个点都同理
奇数个点也无妨,目标点即为最中间的呢个点,剩下的偶数个点一前一后对应相减即可
*/
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static Scanner sc=new Scanner(System.in);
static int n=sc.nextInt();
static int a[]=new int[n];
static long ans;
public static void main(String[] args) {
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
}
Arrays.sort(a);
if(n%2==0) { //偶数个点,排序后一前一后对应相减即可
for(int i=0;i<n/2;i++) {
ans+=a[n-1-i]-a[i];
}
System.out.println(ans);
System.exit(0);
}else { //奇数个点,除去最中间的点之后一前一后对应相减即可
for(int i=0;i<(n-1)/2;i++) {
ans+=a[n-1-i]-a[i];
}
System.out.println(ans);
}
}
}