#P1112. [POI2008]砖块Klo

    ID: 110 传统题 1000ms 128MiB 尝试: 2969 已通过: 727 难度: 5 上传者: 标签>CF1800普及+/提高-中位数最小化绝对偏差和滑动窗口有序多重集合增量维护

[POI2008]砖块Klo

题目描述

NN 柱砖,希望有连续 KK 柱的高度是一样的。

你可以选择以下两个动作 :

  • 从某柱砖的顶端拿一块砖出来,丢掉不要了.。
  • 从仓库中拿出一块砖,放到另一柱。

仓库无限大,现在希望用最小次数的动作完成任务。

输入格式

第一行给出 NN , K(1≤k≤n≤100000)K (1 \le k \le n \le 100000), 下面 NN 行,每行代表这柱砖的高度 hi(0≤hi≤1000000)h_i (0 \le hi \le 1000000)。

输出格式

一行,输出最小的动作次数。

5 3
3
9
2
3
1
2

提示

原题还要求输出结束状态时每柱砖的高度,本题略去。

题目来源

没有写明来源