Lập đội tối đa
Đề bài
Mô tả
Có lập trình viên, người thứ có kỹ năng . Bạn muốn chia họ thành một số đội (mỗi đội không rỗng) sao cho số đội lập được là lớn nhất.
Mỗi đội phải thoả điều kiện: số lượng thành viên trong đội nhân với kỹ năng nhỏ nhất trong số các thành viên của đội phải không nhỏ hơn .
Mỗi lập trình viên thuộc về nhiều nhất một đội. Một số lập trình viên có thể không thuộc đội nào.
Hãy tính số đội tối đa có thể lập được.
Dữ liệu vào
- Dòng đầu chứa số nguyên , số lượng bộ dữ liệu.
- Với mỗi bộ dữ liệu:
- Dòng đầu chứa hai số nguyên và , số lượng lập trình viên và giá trị ràng buộc.
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên là số đội tối đa có thể lập được.
Ràng buộc
- Tổng của trên tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 10 7 11 2 9 5 4 8 2 4 2 3 4 11 1 3 3 7 |
2 1 0 |
Bộ 1: đội {11} có , đội {7, 9} có , được 2 đội. Bộ 2: cả 4 người tạo 1 đội . Bộ 3: không lập được đội nào. |
| 3 6 6 3 3 3 3 3 3 5 1 1 1 1 1 1 3 1000000000 1000000000 1000000000 1000000000 |
3 5 3 |
Bộ 1: mỗi 2 người tạo 1 đội (), được 3 đội. Bộ 2: nên mỗi người là một đội. Bộ 3: mỗi người kỹ năng tự tạo một đội. |
Bình luận