Chuyển cây bạch đàn (kỹ thuật cửa sổ trượt)

Xem dạng PDF

Gửi bài giải

Điểm: 3,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Nhà Tít ở gần sông, trên bờ sông có trồng N cây bạch đàn, tuy nhiên nhiều cây bạch đàn không thể sống được do ngập lụt gió bão gần bờ sông. Một ngày nọ Tít tha thẩn bên bờ sông và tự hỏi liệu có thể tìm thấy K cây bạch đàn còn sống liên tiếp hay không? Nếu không tìm được Tít có thể chuyển các cây bạch đàn ở những chỗ khác để tạo thành K cây bạch đàn còn sống liên tiếp. Bạn hãy giúp Tít di chuyển ít nhất số cây bạch đàn để tạo thành K cây bạch đàn còn sống liên tiếp, hoặc có thể đưa ra kết luận rằng không thể di chuyển cây bạch đàn để tạo thành K cây bạch đàn còn sống liên tiếp.


Ràng buộc: ~1 \leq K \leq N \leq 10^6~


Output: In ra số cây bạch đàn ít nhất cần chuyển hoặc in ra NO nếu không thể chuyển được để tạo thành K cây còn sống liên tiếp


Input 01:
11 3
0 0 0 0 1 0 1 0 0 0 1

Giải thích: 0 là cây bạch đàn bị chết, 1 là cây còn sống

Output 01:
1

Giải thích: Cần chuyển ít nhất 1 cây

Input 02:
11 4
0 0 0 0 1 0 1 0 0 0 1
Output 02:
NO

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.