Số lượng hộp cần thiết
Xem dưới dạng PDFCó \(n\) vật dụng. Vật dụng thứ \(i\) có chiều dài \(l_i \le l\) với \(l\) là chiều dài của các hộp. Tìm số lượng hộp nhỏ nhất \(q\) sao cho:
- Mỗi hộp chứ nhiều nhất \(2\) vật dụng.
- Mỗi vật dụng đều phải được cho vào hộp.
- Tổng chiều dài các vật dụng trong hộp không vượt quá chiều dài của hộp là \(l\).
Ghi chú: Các vật dụng có bề rộng như nhau và vừa khít bề rộng của hộp.
Hình minh họa cho input mẫu:
Input Dòng đầu tiên cho biết số lượng bộ test. Theo sau là 1 dòng trống và giữa 2 bộ test cũng có 1 dòng trống.
- Dòng đầu tiên của bộ test là số lượng vật dụng \(n\) với (\(1 \le n \le 10^5\)).
- Dòng thứ hai là chiều dài hộp \(l\) với (\(l \le 10000\)).
- \(n\) dòng tiếp theo cho biết chiều dài của \(n\) vật dụng.
Output
- Với mỗi bộ test, ouput ra số lượng hộp ít nhất cần sử dụng.
- Giữa output của 2 bộ test có 1 dòng trống.
Input mẫu
1
10
80
70
15
30
35
10
80
20
35
10
30Output mẫu
6
Nhận xét
AC bài cũ rồiii, level uppp>:))))))))))))