Mô tả
Nhà máy thép Hòa Phát tại Dung Quất luôn ăn centralized điện năng. Trạm EVN đo sản lượng tại cột điện, còn bộ đo PLC nội bộ nhà máy tự đếm điện năng tiêu thụ. Sự chênh lệch tức thời giữa hai số liệu gọi là delta điện năng (có thể âm hoặc dương).
Để đảm bảo tính chính xác của thiết bị, kỹ sư nhà máy cần kiểm tra xem có tồn tại đoạn thời gian ngắn nhất (tính bằng số mốc đo liên tiếp) mà tổng delta điện năng đạt đến một ngưỡng cảnh báo an toàn cho trước hay không.
Cụ thể, cho một mảng số nguyên biểu diễn delta điện năng tại các mốc thời gian liên tiếp, và một số nguyên ngưỡng cảnh báo. Bạn cần tìm độ dài (số phần tử) của mảng con ngắn nhất sao cho tổng các phần tử trong mảng con đó lớn hơn hoặc bằng ngưỡng.
Nếu không có mảng con nào thỏa mãn, trả về 0.
Đầu vào
- Dòng đầu tiên chứa số nguyên dương
n(số lượng mốc đo thời gian). - Dòng thứ hai chứa
nsố nguyên cách nhau bởi khoảng trắng, là các giá trị delta điện năng tại từng mốc. - Dòng thứ ba chứa một số nguyên
s(ngưỡng cảnh báo).
Đầu ra
- Một số nguyên duy nhất là độ dài mảng con ngắn nhất thỏa mãn tổng ≥ ngưỡng
s, hoặc 0 nếu không tồn tại.
Ràng buộc
- 1 ≤ n ≤ 10^5
- -10^6 ≤ mỗi giá trị delta ≤ 10^6
- 1 ≤ s ≤ 10^9
- Tổng các phần tử trong mảng không vượt quá 10^9 về giá trị tuyệt đối.
Ví dụ
Ví dụ 1:
Input: 6 2 3 1 2 4 3 7
Output: 2
Giải thích: Mảng delta gồm [2, 3, 1, 2, 4, 3]. Cần tìm mảng con ngắn nhất có tổng ≥ 7.
- Xét mảng con [4, 3] (2 phần tử cuối): tổng = 4 + 3 = 7 ≥ 7. Độ dài = 2.
- Các mảng con ngắn hơn (độ dài 1) đều có tổng < 7. Vậy đáp án là 2.