Python - Số nhóm kích thước K tối đa với các loại vật phẩm riêng biệt

Cho mảng counts (counts[i] = số lượng vật loại i) và k. Tìm số nhóm kích thước k tối đa sao cho mỗi nhóm chứa k loại vật khác nhau.

Ví dụ

Input: counts = [2, 3, 5, 3], k = 2
Output: 6
Giải thích: 4 loại a,b,c,d. Các nhóm: (c,a), (b,a), (c,b), (c,b), (d,a), (d,a) = 6 nhóm.

Thuật toán: Binary Search + Kiểm tra tham lam

Hàm possible(groups): có thể tạo groups nhóm không?

• Mỗi nhóm cần k loại khác nhau → tổng cần = groups * k
• Mỗi loại i có thể đóng góp tối đa min(counts[i], groups) (vì 1 nhóm chỉ dùng 1 loại 1 lần)
• Duyệt các loại, trừ dần required. Nếu về 0 → có thể.

Mã Python

def possible(counts, groups, k):
    required = groups * k
    for c in counts:
        take = min(c, groups, required)
        required -= take
        if required == 0:
            return True
    return False

def solve(counts, k):
    res = 0
    l, r = 0, sum(counts)
    while l <= r:
        m = l + (r - l) // 2
        if possible(counts, m, k):
            l = m + 1
            res = max(res, m)
        else:
            r = m - 1
    return res

# Test
counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k))  # Output: 6

Phân tích độ phức tạp

• Kiểm tra possible: O(n)
• Binary search: O(log(sum(counts)))
• Tổng: O(n log S) - S = tổng số vật
• Không gian: O(1)

Chứng minh tính đúng đắn

Giả sử có thể tạo g nhóm. Mỗi loại i xuất hiện tối đa min(counts[i], g) lần (vì mỗi nhóm chỉ chứa 1 vật loại i). Tổng vật phẩm có sẵn = sum(min(counts[i], g)). Cần ≥ g * k. Điều kiện cần và đủ.

Bài toán gốc: LeetCode 2233 - Maximum Number of Groups With Length K (tương tự).