Hướng dẫn giải của Chia Đội Cân Bằng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Chia Đội Cân Bằng

Hướng tiếp cận

Vì chỉ có $12$ người, số cách phân chia hợp lệ nhỏ — có thể duyệt toàn bộ.

Nhận xét quan trọng

Số hoán vị của nhãn đội ${0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3}$ là $\frac{12!}{(3!)^{4}} = 369600$ . Con số này rất nhỏ.
Dùng next_permutation trên mảng nhãn để duyệt tất cả cách gán người vào đội một cách hiệu quả (tự bỏ qua trùng lặp).
Có thể tối ưu thêm bằng backtracking với cắt tỉa: nếu hai đội có cùng số người và tổng điểm, chúng là hoán đổi được — bỏ qua.

Thuật toán

Cách 1 — next_permutation (đơn giản):

Tạo mảng nhãn $[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]$ .
Duyệt tất cả hoán vị duy nhất.
Với mỗi hoán vị, tính tổng từng đội và cập nhật đáp án.

Cách 2 — Backtracking với cắt tỉa:

Sắp xếp kỹ năng giảm dần.
Gán lần lượt từng người vào một trong $4$ đội (mỗi đội tối đa $3$ người).
Cắt tỉa: không gán vào đội có cùng trạng thái với đội đã xét trước đó.

Độ phức tạp

Thời gian: $O (\frac{12!}{(3!)^{4}}) = O (369600)$
Bộ nhớ: $O (1)$

Bình luận

Không có bình luận tại thời điểm này.