โปรแกรมหาจำนวนกลุ่มสูงสุดขนาด K ที่มีไอเทมชนิดต่างกันได้ใน Python

ปัญหา

ให้รายการ counts ที่ counts[i] แสดงจำนวนไอเทมชนิดที่ i และค่า k ให้หาจำนวนกลุ่มสูงสุดขนาด k ที่แต่ละกลุ่มต้องมีไอเทมชนิดต่างกันหมด

ตัวอย่าง

Input: counts = [2, 3, 5, 3], k = 2
Output: 6

# ชนิด a,b,c,d มีจำนวน 2,3,5,3
# กลุ่มที่เป็นไปได้: (c,a), (b,a), (c,b), (c,b), (d,a), (d,a) = 6 กลุ่ม

อัลกอริทึม: Binary Search + Greedy Check

1. ฟังก์ชัน possible(groups): ตรวจสอบว่าสร้างกลุ่มจำนวน groups ได้หรือไม่
   • ต้องการไอเทมทั้งหมด required = groups * k
   • จากแต่ละชนิด ใช้ได้สูงสุด min(counts[i], groups, required) ชิ้น (ไม่สามารถใช้ชนิดเดียวซ้ำในกลุ่มเดียวกัน)
   • ลบ required ทีละชนิด จนเหลือ 0 → สร้างได้
2. Binary Search หาค่า groups สูงสุดในช่วง [0, sum(counts)]

ตัวอย่างโค้ด

def possible(counts, groups, k):
    required = groups * k
    for i in range(len(counts)):
        temp = min(counts[i], groups, required)
        required -= temp
        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

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

ความซับซ้อน

• เวลา: O(n log S) โดย S = sum(counts)
• พื้นที่: O(1)

อินพุต / เอาต์พุต

Input: [2, 3, 5, 3], 2
Output: 6