Chương trình tìm giá trị lớn nhất của nhóm nhỏ nhất khi chia mảng thành k nhóm liên tiếp trong Python

Cho mảng nums và số k. Chia mảng thành k nhóm liên tiếp. Nhóm nhỏ nhất là nhóm có tổng nhỏ nhất. Tìm giá trị lớn nhất có thể của nhóm nhỏ nhất đó.

Ví dụ: nums=[2,6,4,5,8], k=3 → 8 (chia: [2,6], [4,5], [8]).

Giải thuật (Binary Search + Kiểm tra tham lam)

1. Hàm is_divisible(target): duyệt mảng, tích lũy tổng. Khi sum >= target → cắt nhóm, reset tổng. Nếu tạo được ≥ k nhóm → True.
2. Binary search target trong [1, sum(nums)//k + 1].

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        def is_divisible(target):
            if target <= 1:
                return True
            chunks = 0
            cur = 0
            for x in nums:
                cur += x
                if cur >= target:
                    cur = 0
                    chunks += 1
                    if chunks == k:
                        return True
            return False
        
        left, right = 1, 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))  # Output: 8

Đầu vào / Đầu ra

Input: [2, 6, 4, 5, 8], 3

Output: 8