Mô tả
Kỹ sư FPT Telecom đang giám sát băng thông đường truyền GPON tại một cụm tòa nhà chung cư cao cấp ở Cầu Giấy, Hà Nội. Hệ thống ghi lại lưu lượng mạng (đơn vị Mbps) tại từng khung giờ liên tiếp trong một ngày. Do đặc thù hạ tầng GPON, khi tổng lưu lượng trên K khung giờ liên tiếp vượt ngưỡng cho phép, bộ chia quang sẽ rơi vào trạng thái quá tải gây rớt gói tin.
Để preventive maintenance, kỹ sư cần tìm ra K khung giờ liên tiếp có tổng lưu lượng nhỏ nhất — tức khoảng thời gian "nhàn nhất" — để lên lịch chạy các tác vụ bảo trì nặng như đồng bộ sao lưu và cập nhật firmware cho OLT. Bạn hãy viết chương trình tìm vị trí bắt đầu (chỉ số từ 0) của cửa sổ K phần tử liên tiếp có tổng nhỏ nhất. Nếu có nhiều cửa sổ cùng tổng nhỏ nhất, chọn vị trí bắt đầu nhỏ nhất.
Đầu vào
Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 10^5), lần lượt là số khung giờ và độ dài cửa sổ.
Dòng thứ hai chứa n số nguyên a[0], a[1], ..., a[n-1] là lưu lượng tại từng khung giờ, mỗi số có |a[i]| ≤ 10^6.
Đầu ra
In ra một số nguyên duy nhất là chỉ số bắt đầu (từ 0) của cửa sổ K phần tử liên tiếp có tổng nhỏ nhất.
Ràng buộc
1 ≤ k ≤ n ≤ 10^5|a[i]| ≤ 10^6- Tổng các phần tử trong bất kỳ cửa sổ nào đều nằm trong khoảng
[-10^9, 10^9], an toàn với số nguyên 64-bit.
Ví dụ
Ví dụ 1:
Input: 8 3 12 5 7 3 8 2 10 4
Output: 3
Giải thích: Có 6 cửa sổ độ dài 3:
- Vị trí 0: 12 + 5 + 7 = 24
- Vị trí 1: 5 + 7 + 3 = 15
- Vị trí 2: 7 + 3 + 8 = 18
- Vị trí 3: 3 + 8 + 2 = 13 (nhỏ nhất)
- Vị trí 4: 8 + 2 + 10 = 20
- Vị trí 5: 2 + 10 + 4 = 16
Tổng nhỏ nhất là 13 tại vị trí bắt đầu 3.
Ví dụ 2:
Input: 5 5 -3 -7 -1 -2 -4
Output: 0
Giải thích: Chỉ có một cửa sổ độ dài 5, bao trọn cả mảng, tổng = -3 + (-7) + (-1) + (-2) + (-4) = -17. Vị trí bắt đầu là 0.