KKDD - K - Không đơn độc

Giới hạn
  • Thời gian: 0.6s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Một dãy số được gọi là K – không đơn độc nếu mỗi phần tử của dãy đều thuộc một đoạn gồm ít nhất K phần tử liên tiếp có giá trị giống nhau. Ví dụ dãy 1 1 2 2 2 1 1 là 2 – không đơn độc , nhưng không phải là 3 – không đơn độc vì phần tử đầu tiên chỉ thuộc một đoạn gồm 2 số 1. Nếu một dãy số chưa phải là K – không đơn độc , bạn có quyền thực hiện các thao tác biến đổi, mỗi thao tác sẽ cộng ( hoặc trừ ) một đơn vị vào một phần tử của dãy.

Yêu cầu

Hãy đếm số thao tác ít nhất cần thực hiện để biến một dãy số thành dãy K – không đơn độc .

Dữ liệu

  • Dòng đầu ghi 2 số N, K. N là số lượng phần tử của dãy số.
  • Dòng sau ghi N số tự nhiên thể hiện dãy số.

Kết quả

  • Gồm một dòng duy nhất ghi ra số thao tác cần thực hiện.

Ví dụ 

Dữ liệu
7 3
2 2 3 4 4 5 5

Kết quả
3

Giới hạn

  • 1 ≤ N ≤ 10000
  • 1 ≤ K ≤ 100
  • K ≤ N
  • Phần tử của dãy có giá trị không quá 10 9

Hạn chế

  • Có 30% số test thỏa mãn N ≤ 200.
  • Có 50% số test thỏa mãn N ≤ 2000.

  • Người up: voj
  • Nguồn bài: VNOI Online Informatics Olympiad '09Day 2