Tutorial — Organizing Research Squads

Hãy chú ý đến mối quan hệ giữa năng lực của các nhà nghiên cứu và số lượng thành viên tối thiểu cần thiết để tạo thành một nhóm hợp lệ. Một nhà nghiên cứu có chỉ số năng lực càng cao thì nhóm chứa người đó càng cần ít thành viên hơn.

Nếu chúng ta xếp các nhà nghiên cứu theo thứ tự năng lực giảm dần, việc gom các nhà nghiên cứu có năng lực cao nhất còn lại vào cùng một nhóm sẽ luôn làm tăng chỉ số năng lực nhỏ nhất của nhóm đó. Khi nhóm tích lũy đủ $k$ thành viên sao cho $k \cdot a_i \ge x$, ta nên chốt nhóm ngay lập tức để tiết kiệm nhân lực cho các nhóm sau.

Thuật toán tham lam kết hợp sắp xếp là phương pháp tối ưu cho bài toán này. Sắp xếp mảng năng lực giảm dần, sau đó duyệt qua mảng và duy trì kích thước nhóm hiện tại $k$; mỗi khi $k \cdot a_i \ge x$, tăng số lượng nhóm lên $1$ và đặt $k = 0$.