Cho batchSize và mảng groups (groups[i] = số khách nhóm i). Cửa hàng làm bánh theo lô batchSize, phải phân hết lô trước khi làm lô mới. Mỗi khách 1 bánh. Nhóm vào được phục vụ hết trước nhóm sau. Nhóm "vui" nếu khách đầu tiên nhận bánh tươi (không phải dư lô trước). Có thể sắp xếp lại thứ tự nhóm. Tìm số nhóm vui tối đa.
Ví dụ: batchSize = 4, groups = [2,1,8,4,3] → output = 4 (sắp xếp [8,4,2,3,1]).
Giải thuật (DP trên trạng thái modulo + Count)
- Chỉ quan tâm groups[i] % batchSize. Đếm tần suất mỗi remainder.
- DP(state_tuple, current_sum_mod) = max happy groups từ trạng thái còn lại.
- Thử lấy từng remainder k còn > 0, cập nhật state, đệ quy.
- Nếu current_sum_mod == 0 thì nhóm tiếp theo sẽ vui (+1).
- Memoization trên state tuple.
Code Python
from collections import Counter
def solve(batchSize, groups):
l = [g % batchSize for g in groups]
count = Counter(l)
g = [count[i] for i in range(batchSize)]
from functools import lru_cache
@lru_cache(None)
def dp(sm, t):
if max(t) == 0:
return 0
ans = 0
arr = list(t)
for k in range(batchSize):
if arr[k] == 0:
continue
arr[k] -= 1
ans = max(ans, dp((sm + k) % batchSize, tuple(arr)))
arr[k] += 1
return ans + (sm == 0)
return dp(0, tuple(g))
batchSize = 4
groups = [2, 1, 8, 4, 3]
print(solve(batchSize, groups)) # 4
Đầu vào / Đầu ra
Input: 4, [2,1,8,4,3]
Output: 4