Một cầu cảng có \(n\) gói hàng được đánh số từ 1 đến \(n\). Gói hàng thứ \(i\) có trọng lượng \(a_{i}\), các gói hàng được đặt trên băng chuyền theo tuần tự từ 1 đến \(n\) và lần lượt đưa lên các kiện hàng. Băng chuyền có một hệ số hoạt động \(k\), trong quá trình vận hành nếu các gói hàng liên tiếp có trọng lượng không vượt quá k thì băng chuyền cho vào cùng một kiện hàng, sau đó băng chuyền chuyển sang kiện hàng tiếp theo. Ban quản lý cảng biển muốn khảo sát các hệ số hoạt động \(k\) để tính số gói hàng nhiều nhất của một kiện hàng.
Yêu cầu: Cho trọng lượng của \(n\) gói hàng và \(q\) số nguyên dương \(k\) là hệ số hoạt động của băng chuyền cần khảo sát. Với mỗi số nguyên dương k hãy tính số gói hàng nhiều nhất của một kiện hàng.
Dữ liệu vào:
+ Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\ (1\ \leq \ n,\ q\ \leq 10^{5})\);
+ Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ ...,\ a_{n}\ (1 \leq a_{i} \leq 10^{9})\) là trọng lượng của các gói hàng;
+ \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\ (1 \leq k \leq 10^{9})\).
Kết quả:
+ Ghi trên \(q\) dòng, mỗi dòng ghi một số nguyên dương tương ứng là kết quả tính được theo dữ liệu vào.
Ví dụ:
Input | Output | Giải thích |
---|---|---|
6 3 4 2 3 5 8 1 4 12 2 | 3 6 1 | Với k = 4: Kiện hàng nhiều gói hàng nhất tìm được có 3 gói hàng liên tiếp trọng lượng không lớn hơn 4 là: 4, 2, 3; Với k = 12: Tất cả 6 gói hàng có trọng lượng nhỏ hơn 12 nên vào cùng 1 kiện hàng; Với k = 2: Có 2 kiện hàng có cùng số gói hàng là 1. |
Ràng buộc:
+ Có 20% số test ứng với 20% số điểm thỏa mãn: \(q\ = \ 1,\ n\ \leq 10^{2}\);
+ 40% số test khác ứng với 40% số điểm thỏa mãn: \(q,\ n\ \leq \ 10^{3}\);
+ 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.
Code tích cực |
---|
Trong 24h |
Trong 7 ngày |
|
Trong 30 ngày |
|
Thống kê |
---|
AC/Sub: 97887/180710 Pascal: 17121 C++: 130348 Python: 33199 Lượt xem/tải tests: 38905 |