1.9 货仓选址问题——Python
2021-03-07 14:31
标签：建立 引用 不难 inpu 区间 均值 16px div 判断 在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。 输入格式 第一行输入整数N。 第二行N个整数A1~AN。 输出格式 输出一个整数，表示距离之和的最小值。 数据范围 1≤N≤100000, 输入样例 输出样例 这是一道非常基础的算法题，要求一个货仓到每家商店的最短距离，我的思路如下： 1. 我们要找一个仓库，他们在一条路线上 2. 如果是二维的，我们就要一个一个进行判断计算，因为他要求所有的最短距离。但是这道题是一维，所以首先需要求出货仓的坐标 3. 不难分析，当货仓处于所有商店最中间的位置时，到每家商户的距离将会最近，即货仓处于的位置应该是商店坐标的中位数。 假设区间[a,b]的距离;是n那么如果货仓x选在区间[a,b]的任一位置的话，s=n;如果选在区间[a,b]之外的话，s>n。 因此货仓应选在两个点之间，推广到n个商店的情况的话，货仓应该选在最中间的两个点之间，此时的s-定是最小的(可以用反证法证明)。当商店个数是奇数时，中位数只有一个; 当个数是偶数时，中位数有两个，此时可以取两个中位数的平均值，或是直接取整** 4. 确定了货仓的坐标之后，就可以通过将货仓的坐标和每个商店的坐标相减取绝对值再加和，得到货仓到每家商店的最短距离 1. 一维数组的输入方式： 或者是： 2. 求中位数的方式： ① 可以通过导入numpy包，引用其中的median()函数直接求得中位数。 ② 也可以通过移位运算符： >> ，移位运算符针对二进制数进行左移或右移，即移动的单位是二的幂次方。假设 n = 8，其二进制为 0000 1000 ，则 n >> 1为 n 向右移2^1，即 0000 0100，此时得到的结果是4，可以直接取得中位数。 1.9 货仓选址问题——Python 标签：建立 引用 不难 inpu 区间 均值 16px div 判断 原文地址：https://www.cnblogs.com/zyd-994264926326/p/14261536.html题目描述
0≤Ai≤400004
6 2 9 1
12
题目分析
源代码
1 # import numpy as np
2
3 n = int(input())
4 # 两种输入方式
5 # nums = list(map(int, input().split()))
6 arr = input("")
7 nums = [int(i) for i in arr.split()]
8
9 # 对输入的数组进行排序
10 nums.sort()
11
12 # 两种求中位数方式
13 address = nums[n >> 1]
14 # address = np.median(nums)
15
16 res = 0
17 for num in nums:
18 res += abs(num - address)
19 print(res)
注意问题
nums = list(map(int, input().split()))
arr = input("")
nums = [int(i) for i in arr.split()]
import numpy as np
nums = [6, 5, 8, 2]
address = np.median(nums)
address = nums[n >> 1]
文章标题：1.9 货仓选址问题——Python
文章链接：http://soscw.com/index.php/essay/61379.html