给出一列数,找出p对数字(每个数只能最多用一次),问这p对数字两两之差之和最小多少,直接二分结果,若想两两之差小,那么就是sort之后每次选相邻的数
1 #2616
2 #Runtime: 831 ms (Beats 100%)
3 #Memory: 25.4 MB (Beats 100%)
4
5 class Solution(object):
6 def minimizeMax(self, nums, p):
7 """
8 :type nums: List[int]
9 :type p: int
10 :rtype: int
11 """
12 n = len(nums)
13 nums.sort()
14 l, r = 0, nums[-1] - nums[0]
15
16 def cal(dif):
17 nt = 0
18 i = 1
19 while i < len(nums):
20 if nums[i] - nums[i - 1] <= dif:
21 i += 1
22 nt += 1
23 i += 1
24 return nt
25
26 while l < r:
27 mid = (l + r) // 2
28 if cal(mid) >= p:
29 r = mid
30 else:
31 l = mid + 1
32 return l