服务中心选址问题

本文主要是介绍服务中心选址问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

服务中心的位置记为location，区域由[left,right]表示，服务中心到区域的距离为：

1. 如果right < location，则距离为location - right
2. 如果location < left，距离为left - location
3. 如果left <= location <= right，则距离为0

输入：
第一行，一个整数N表示区域个数。
后面N行，每行两个整数，表示区域的左右起点终点。

输出：
一个整数，表示服务中心位置到所有区域的距离总和的最小值

题目分析

1. 输入的区域包含交集
2. 经过例子发现规律，距离之和最小的location在输入的所有区间left和right排序后的中间两个数组成的区间上。
3. 例如：[1,2],[4,7],[5,20] 排序后为1,2,4,5,7,20，中间的两个数为4,5，则4<=location<=5时，距离最小；[1,3],[2,4],[4,5],[6,20],排序后1,2,3,4,4,5,6,20，中间两个数是4,4，则location=4，距离之和最小，为3

代码实现

size = int(input().strip())
rows = []
datas = []
for i in range(size):a, b = map(int, input().strip().split(' '))datas.append(a)datas.append(b)rows.append((a, b))
datas.sort()
i = len(datas) // 2 - 1
location = datas[i]
distance = 0
for start, end in rows:if location > end:distance += location - endelif location < start:distance += start - locationprint(distance)

这篇关于服务中心选址问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---