华为OD机试 - 新学校选址（Python/JS/C/C++ 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
为了缓解学期开学生暴涨的问题，小乐村要建立所新学校，考虑到学生上学安全问题，需要所有学生到学校的距离最短。
假设学校和所有学生家都在一条直线上，请问学校建立在什么位置，能够保证到学校到各个学生家的距离和最短。
二、输入描述
第一行：整数 n 取值范围 [1,1000]，表示有 n 户家庭。
第二行：一组整数 m 取值范围 [0,10000]，表示 n 户家庭的位置，所有家庭的位置都不相同。
三、输出描述
一个整数，确定的学校的位置。
如果有多个位置，则输出最小的。
四、测试用例
测试用例1：
1、输入
5
0 20 40 10 30
2、输出
20
3、说明
20到各个家庭的距离分别为20 0 20 10 10，总和为60，最小
测试用例2：
1、输入
1
20
2、输出
20
3、说明
只有一组数据，20到20距离最小，为0
五、解题思路
为了找到一个位置，使得所有学生家到学校的距离和最小，可以利用中位数的性质。在一维空间中，选择中位数位置可以最小化所有点到该位置的绝对距离之和。具体步骤如下：
- 输入处理：读取家庭数量 n 以及 n 个家庭的位置。
- 排序：将家庭位置进行排序。
- 选择中位数：
- 如果 n 为奇数，选择排序后的中间位置作为学校的位置。
- 如果 n 为偶数，选择中间左边的那个位置（较小的中位数）作为学校的位置，以满足“如果有多个位置，则输出最小的”要求。
- 输出结果：输出选定的学校位置。
六、Python算法源码
# 导入sys模块以便读取输入
import sys
def main():
# 读取所有输入，并按空白字符分割
input = sys.stdin.read().split()
# 第一个输入为家庭数量n，转换为整数
n = int(input[0])
# 接下来的n个输入为家庭的位置，转换为整数列表
positions = list(map(int, input[1:n+1]))
# 对位置列表进行排序
positions.sort()
# 如果n为奇数，选择中间位置的值作为学校位置
if n % 2 == 1:
school_position = positions[n // 2]
else:
# 如果n为偶数，选择中间左边的那个位置（较小的中位数）
school_position = positions[(n // 2) - 1]
# 输出学校的位置
print(school_position)
# 调用主函数
if __name__ == "__main__":
main()
七、JavaScript算法源码
// 使用readline模块读取输入
const readline = require('readline');
// 创建接口以逐行读取输入
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
// 监听每一行的输入
rl.on('line', (line) => {
input = line.trim().split(' ').map(Number);
// 关闭输入流，开始处理
rl.close();
});
// 当输入流关闭时执行
rl.on('close', () => {
// 第一个数字为家庭数量n
const n = input[0];
// 接下来的n个数字为家庭的位置
const positions = input.slice(1, n + 1);
// 对位置进行排序
positions.sort((a, b) => a - b);
let schoolPosition;
if (n % 2 === 1) {
// 如果n为奇数，选择中间位置
schoolPosition = positions[Math.floor(n / 2)];
} else {
// 如果n为偶数，选择中间左边的那个位置
schoolPosition = positions[(n / 2) - 1];
}
// 输出学校的位置
console.log(schoolPosition);
});
八、C算法源码
#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {
// 将void指针转换为int指针，并比较值
return (*(int*)a - *(int*)b);
}
int main() {
int n;
// 读取家庭数量n
scanf("%d", &n);
// 动态分配内存存储n个家庭的位置
int *positions = (int*)malloc(n * sizeof(int));
// 读取n个位置
for(int i = 0; i < n; i++) {
scanf("%d", &positions[i]);
}
// 使用qsort对位置数组进行排序
qsort(positions, n, sizeof(int), compare);
int school_position;
if(n % 2 == 1) {
// 如果n为奇数，选择中间位置
school_position = positions[n / 2];
}
else {
// 如果n为偶数，选择中间左边的那个位置
school_position = positions[(n / 2) - 1];
}
// 输出学校的位置
printf("%d\n", school_position);
// 释放分配的内存
free(positions);
return 0;
}
九、C++算法源码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
// 读取家庭数量n
cin >> n;
// 创建一个向量存储n个家庭的位置
vector<int> positions(n);
// 读取n个位置
for(int i = 0; i < n; i++) {
cin >> positions[i];
}
// 对位置进行排序
sort(positions.begin(), positions.end());
int school_position;
if(n % 2 == 1){
// 如果n为奇数，选择中间位置
school_position = positions[n / 2];
}
else{
// 如果n为偶数，选择中间左边的那个位置
school_position = positions[(n / 2) - 1];
}
// 输出学校的位置
cout << school_position << endl;
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
