← 返回题目列表

AtCoder · arc099_a

C. 最小化

中文机器翻译题面 查看原题

分数: 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