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

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

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