Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác là k. Chúng ta phải chia danh sách thành k nhóm liền nhau. Nhóm nhỏ nhất là nhóm có tổng nhỏ nhất trong tất cả các nhóm. Vì vậy, hãy tìm giá trị lớn nhất có thể có của nhóm nhỏ nhất.
Vì vậy, nếu đầu vào là nums =[2, 6, 4, 5, 8] k =3, thì đầu ra sẽ là 8, vì chúng ta có thể chia danh sách thành ba nhóm như:[2, 6], [4 , 5], [8]. Vậy nhóm tối thiểu có tổng là 8.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm is_divosystem (). Điều này sẽ đạt được mục tiêu
-
nếu target <=1 thì
-
trả về True
-
-
num_chunks:=0, current_sum:=0
-
đối với mỗi x trong số, thực hiện
-
current_sum:=current_sum + x
-
nếu current_sum> =target, thì
-
current_sum:=0
-
num_chunks:=num_chunks + 1
-
nếu num_chunks giống với k, thì
-
trả về True
-
-
-
-
trả về Sai
-
Từ phương thức chính, hãy làm như sau -
-
trái:=1
-
right:=(tổng của tất cả các phần tử tính bằng num) / k + 1
-
trong khi trái
-
giữa:=(trái + phải) / 2
-
nếu is_divible (mid) là true, thì
-
left:=mid
-
-
nếu không,
-
right:=mid
-
-
-
quay lại bên trái
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution: def solve(self, nums, k): def is_divisible(target): if target <= 1: return True num_chunks = 0 current_sum = 0 for x in nums: current_sum += x if current_sum >= target: current_sum = 0 num_chunks += 1 if num_chunks == k: return True return False left = 1 right = sum(nums) // k + 1 while left < right - 1: mid = (left + right) // 2 if is_divisible(mid): left = mid else: right = mid return left ob = Solution() nums = [2, 6, 4, 5, 8] k = 3 print(ob.solve(nums, k))
Đầu vào
[2, 6, 4, 5, 8], 3
Đầu ra
8