摘要
Title: 104. 货仓选址
Tag: 贪心、中位数、绝对值不等式
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

104. 货仓选址

• 题意

  在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
  现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
  为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

• 思路

  绝对值不等式：

  $$|x- a| + |x-b| \ge |a-b|$$

  结论：将所有点排个序，选中位数即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-15 16:19:02
  FilePath: \ACM\Acwing\104.py
  LastEditTime: 2022-03-15 16:19:03
  '''
  n = int(input())
  
  nums = list(map(int, input().split()))
  nums.sort()
  
  pivot = nums[n // 2]
  ans = 0
  for num in nums:
      ans += abs(num - pivot)
  
  print(ans)