(A卷,100分)- 新学校选址（Java & JS & Python）

题目描述

为了解新学期学生暴涨的问题,小乐村要建立所新学校，
考虑到学生上学安全问题,需要所有学生家到学校的距离最短。
假设学校和所有学生家都走在一条直线之上,请问学校建立在什么位置，
能使得到学校到各个学生家的距离和最短。

输入描述

第一行: 整数 n 取值范围 [1 ,1000 ],表示有 n户家庭。
第二行: 一组整数 m 取值范围 [0, 10000 ] ，表示每户家庭的位置，所有家庭的位置都不相同。

输出描述

一个整数，确定的学校的位置。
如果有多个位置，则输出最小的。

用例

题目解析

0 + 10 + 20 + 30 + 40 = 100

10 + 0 + 10 +20 + 30 = 70

20 + 10 +0 + 10 + 20 = 50 

将学校建在30，40点上，其实和建在10，0点上相同，此处不再赘述。

因此，我们发现，将学校建在所有学生家位置的共同中心点位置的距离最短。

本题其实就是中位数定理。

本题通过率100%，反馈的考友使用的是Java编程语言。 

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const n = lines[0] - 0;
    const arr = lines[1].split(" ").map(Number);

    console.log(getResult(arr, n));
    lines.length = 0;
  }
});

function getResult(arr, n) {
  arr.sort((a, b) => a - b);
  const len = arr.length;

  if (len % 2 === 0) {
    const mid = len / 2;
    return arr[mid - 1]; // 取最小的
  } else {
    return arr[Math.floor(len / 2)];
  }
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    System.out.println(getResult(arr));
  }

  public static int getResult(int[] arr) {
    Arrays.sort(arr);

    int len = arr.length;
    if (len % 2 == 0) {
      int mid = len / 2;
      return arr[mid - 1];
    } else {
      return arr[len / 2];
    }
  }
}

Python算法源码

import math

# 输入获取
n = int(input())
arr = list(map(int, input().split()))


# 算法入口
def getResult(arr, n):
    arr.sort()

    if n % 2 == 0:
        mid = int(n / 2)
        return arr[mid - 1]
    else:
        return arr[math.floor(n / 2)]


# 算法调用
print(getResult(arr, n))

判定满分JS答案是错误的验证过程

我的JS解法应该是没有问题的，但是有考友反馈通过率只有83%，因此我去找了本题JS的满分解题代码，如下：

// let n = Number(readline());
// let array = readline().split(" ").map(Number);
let n = Number("5");
let array = "0 20 40 10 30".split(" ").map(Number);

let minSite = getMinSite(array);
console.log(minSite);

function getMinSite(array) {
  array.sort();
  if (array.length % 2 == 0) {
    return array[Math.floor(array.length / 2) - 1];
  } else {
    return array[Math.floor(array.length / 2)];
  }
}

这个满分解法的问题其实很明显，熟悉JS的小伙伴应该一眼就能看出来，那就是array.sort()是存在问题的。因为JS数组的sort方法默认情况下是按照字典序排序的。

比如下面用例：

5
10 15 2 25 3

 其中array = [10, 15, 2, 25, 3]

如果使用默认sort方法的话，即进行字典序升序，因此array排序后还是 [10, 15, 2, 25, 3]

然后该满分代码找中位数，就会找到2

但是这个用例，选2作为学校位置的话，到各个学生家的距离：

• 10 – 2
• 15 – 2
• 2 – 2
• 25 – 2
• 3 -2

之和为：8 + 13 + 0 + 23 + 1 = 45

而我的代码使用的排序是 array.sort((a,b) => a-b)

因此，我的代码找的中位数是10

 选10作为学校位置的话，到各个学生家的距离：

• 10 – 10
• 15 – 10
• abs(2 – 10)
• 25 – 10
• abs(3 -10)

之和为：0 + 5 + 8 + 15 + 7 = 35

因此，结果很明显，是满分答案错了。