分数: 300 点
问题陈述
有一个长度为 N: A_1, A_2, ..., A_N。最初,这个序列是一个排列 1, 2, ..., N.
在此序列上,Snuke 可以执行以下操作:
- 选择 K 序列中的连续元素。然后,将每个所选元素的值替换为所选元素中的最小值。
Snuke 希望通过重复上述操作一定次数来使该序列中的所有元素相等。 求出所需的最少操作次数。 可以证明,在该问题的约束下,这个目标总是可以实现的。
约束
- 2 \leq K \leq N \leq 100000
- A_1, A_2, ..., A_N 是一个排列 1, 2, ..., N.
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 ... A_N
输出
打印所需的最少操作数。
示例输入 1
4 3 2 3 1 4
示例输出 1
2
一种最佳策略如下:
-
在第一个操作中,选择第一个、第二个和第三个元素。顺序 A 变为 1, 1, 1, 4.
-
在第二个操作中,选择第二个、第三个和第四个元素。顺序 A 变为 1, 1, 1, 1.
示例输入 2
3 3 1 2 3
示例输出 2
1
示例输入 3
8 3 7 3 1 8 4 6 2 5
示例输出 3
4