AcWing 104. 货仓选址 PY3 二分枚举写法
原题链接
简单
作者:
徐枫月丶
,
2024-04-04 17:15:49
,
所有人可见
,
阅读 3
import bisect
'''
枚举每一个位置 因为位置范围很小只有[0, 40000]
我们可以知道 当商店的位置每一次往右移动一个单位的时候 所有在它当前位置
左边的商店到它的距离都会增加1 同理所有到它位置右边的都会减少1
所有 排序数组 每一次移动之后 使用二分查找寻找在它左 右所有数的数量
同时 要注意 如果移动到的位置恰好有商店存在 距离还要额外减去当前位置的商店数量
'''
n = int(input())
nums = list(map(int, input().split()))
maxn, ans = 40010, sum(nums)
nums.sort()
len_total = ans
for i in range(1, nums[-1] + 1):
le = bisect.bisect_left(nums, i, 0, len(nums))
ri = bisect.bisect_right(nums, i, 0, len(nums))
x1 = ri - le
numle, numri = le, len(nums) - ri
len_total = len_total + numle - numri - (ri - le) # 不存在、则ri=le
ans = min(ans, len_total)
print(ans)