-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
410.py
55 lines (50 loc) · 1.66 KB
/
410.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
__________________________________________________________________________________________________
sample 24 ms submission
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
assert nums
def is_valid(target, nums, m):
s, c = 0, 1
for x in nums:
s += x
if s > target:
s = x
c += 1
if c > m:
return False
# print(s, c, x, m)
return True
low = max(nums)
high = sum(nums)
while low != high:
mid = (low + high) // 2
if is_valid(mid, nums, m):
high = mid
else:
low = mid + 1
# a = [(x, is_valid(x, nums, m)) for x in range(max(nums), sum(nums)+1)]
# print(a)
return low
__________________________________________________________________________________________________
sample 13120 kb submission
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
l = max(nums)
r = sum(nums) + 1
while l < r:
mid = l + (r - l) // 2
cnt = 0
groups = 0
for n in nums:
cnt += n
if cnt > mid:
groups += 1
cnt = n
if cnt > 0:
groups += 1
if groups <= m:
r = mid
else:
l = mid + 1
return l
__________________________________________________________________________________________________