全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：学校的位置
题目描述：为了解决新学期学生暴涨的问题，小乐村要建所新学校。考虑到学生上学安全问题，需要所有学生家到学校距离最短。假设学校和所有的学生家，走在一条直线上。请问，学校要建在什么位置，能使得学校到各个学生家的距离之和最短？
输入描述：
输入的第一行是一个整数N（1<=N<=1000），表示有N户家庭。
输入的第二行是一个数组（0<= <=10000），表示每户家庭的位置，所有家庭的位置都不相同。
输出描述：
输出一行，一个整数，表示你确定的学校位置。如有多个位置相同，则输出值最小的位置。
知识点：数组贪心排序
时间限制：1s 空间限制：256MB 限定语言：不限
示例1
输入：
5
0 20 40 10 30
输出：
20
说明：
20到各个家庭的距离分别为 20 0 20 10 10，总和为 60，最小。
示例2
输入：
1
20
输出：
20
说明：
只有一组数据，20 到 20 距离最小，为 0。
示例3
输入：
2
0 20
输出：
0
说明：
虽然，有多个地方可以选，但是 0 数值最小。
解题思路：
本题是站长在2023年2月份参加的华为OD机考原题的第2题，这道题有两种解法。
思路一：
我们可以先画一个草图，计算出不同点位到学校的位置，求出距离和的最小值即可。由图中可知，将学校建在所有家庭的中心点位置，可以使总距离最短。其实本题考查的就是中位数定理。什么是中位数定理？数学上，如果一个数轴上有若干个点，那么这些点的中位数到各个点的距离之和最短。中位数的性质：所有数与中位数的绝对差之和最小，中位数是数列中间的那个数，或者是中间的那两个数之一。
package com.codernav.demo.hwod.ques;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 学校的位置
* @Description 为了解决新学期学生暴涨的问题，小乐村要建所新学校。考虑到学生上学安全问题，需要所有学生家到学校距离最短。假设学校和所有的学生家，走在一条直线上。请问，学校要建在什么位置，能使得学校到各个学生家的距离之和最短？
* @Author 开发者导航
* @website https://www.codernav.com
* @date 2023/3/30
*/
public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int minSite = getMinSite(nums);
System.out.println(minSite);
}
public static int getMinSite(int[] nums) {
Arrays.sort(nums);
if (nums.length % 2 == 0) {
return nums[nums.length / 2 - 1];
} else {
return nums[nums.length / 2];
}
}
}
思路二：
也可以使用数组贪心排序算法，求解过程可以分为两步：
1、求出数组中的最大值和最小值作为学校可选位置的区间。
2、遍历步骤1中的位置到各学生家位置之和，求出其最小值的位置。
package com.codernav.demo.hwod.ques;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 学校的位置
* @Description 为了解决新学期学生暴涨的问题，小乐村要建所新学校。考虑到学生上学安全问题，需要所有学生家到学校距离最短。假设学校和所有的学生家，走在一条直线上。请问，学校要建在什么位置，能使得学校到各个学生家的距离之和最短？
* @Author 开发者导航
* @website https://www.codernav.com
* @date 2023/3/31
*/
public class Main2_2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
String[] strs = sc.nextLine().split(" ");
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(strs[i]);
}
Arrays.sort(nums);
int start = nums[0]; //学校可选位置最小值
int end = nums[n - 1]; //学校可选位置最大值
int min = Integer.MAX_VALUE; //距离最小值
int position = 0;
for (int i = start; i <= end; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
count += Math.abs(i - nums[j]); //学校到所有学生家的距离和
}
if (count < min) {
min = count;
position = i; //距离较小的记录其位置
}
}
System.out.println(position);
}
}
相关文章
