給出一列數(shù)，找出p對(duì)數(shù)字（每個(gè)數(shù)只能最多用一次），問這p對(duì)數(shù)字兩兩之差之和最小多少，直接二分結(jié)果，若想兩兩之差小，那么就是sort之后每次選相鄰的數(shù)
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