AcWing 3176. 扫地机器人(python,贪心,二分)
原题链接
简单
作者:
atri_17
,
2024-04-12 20:29:07
,
所有人可见
,
阅读 2
解题思路
- 首先,我们可以发现:扫地时间
t
只与包含扫地机所在位置的区间的长度d
有关,且关系为$t=(d-1)*2$
- 然后,我们运用贪心的想法来判断当每个扫地机负责长度为
d
的区间时,能否将整个区域扫完。具体来说,我们先将扫地机的位置从小到大排序,然后建立一个指针p
,指向从左到右第一块没被清扫的区域(初始值为0)。然后遍历所有扫地机,如果长度为d
的区间的右端点是该扫地机的情况下,指针p
仍不在区间内,那么每个扫地机负责长度为d
的区间肯定不能将整个区域扫完;否则,选择$min(p, 扫地机位置)$作为区间左端点,更新p
,遍历下一个扫地机。遍历完以后,还要看此时p
是否大于n-1,若大于,则能将整个区域扫完;若小于,则不能。
- 然后,我们利用二分查找的方法来寻找能将整个区域扫完的最小长度
d
。具体来说,我们先选择左右端点,在最好的情况下,即扫地机分配最均匀时,每个扫地机需负责长度为$n/k$的区间,故选取左端点为$n//k-1$,该长度一定不能将整个区域扫完;在最坏的情况下,即所有扫地机器人都堆在区域的一端时,需要离端点最远的那个扫地机器人负责长度为$n-k+1$的区间才能使扫完整个区域的时间最短,故选取右端点为$n-k+1$,该长度一定能将整个区域扫完。之后,每次选取左右端点的中点用第2步的方法判断是否能将整个区域扫完,若能,则将其作为新的右端点;若不能,则将其作为新的左端点。直到左右端点相差1,此时,左端点为不能将整个区域扫完的最大长度,右端点为能将整个区域扫完的最小长度。
- 最后,将第3步中求出的右端点代表的长度按照第1步中的转换关系转换成时间即为最终答案。
python代码
n, k = map(int, input().split())
num = []
for i in range(k):
num.append(int(input())-1) #使序号从0开始
num.sort()
def is_finish(d):
p = 0
for i in range(k):
if num[i]-p+1 > d:
return False
else:
p = min(p, num[i]) + d
if p>=n:
return True
else:
return False
left = n//k-1
right = n-k+1
while right-left != 1:
mid = (left+right)//2
if is_finish(mid):
right = mid
else:
left = mid
print((right-1)*2)