AcWing 1333. 面试(Python)
原题链接
中等
作者:
多汁炸鸡战士
,
2024-03-04 13:45:55
,
所有人可见
,
阅读 17
二分查找可能的最少人数
时间复杂度 $O(nlognlogn)$
Python 代码
def judge(mid,m,k):
children = l[0:mid]
children.sort()
for window in range(mid-m+1):
if children[window+m-1]-children[window]<=k:
return True
return False
n,m,k = map(int,input().split())
l = list(map(int,input().split()))
left = m
right = n+1
while right>left:
mid = (right+left)//2
if not judge(mid,m,k):
left = mid + 1
else:
right = mid
if left == n+1:
print('impossible')
else:
print(left)