Score : $300$ points

问题描述

存在一个长度为 $N$ 的序列：$A_1, A_2, ..., A_N$。最初，这个序列是 $1, 2, ..., N$ 的一个排列。

在该序列上，Snuke 可以执行以下操作：

• 选择序列中连续的 $K$ 个元素。然后，将所选每个元素的值替换为所选元素中的最小值。

Snuke 希望通过重复上述操作若干次，使得序列中的所有元素都相等。请找出所需的最少操作次数。可以证明，在本题的约束条件下，这一目标总是能够实现的。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a sequence of length $N$: $A_1, A_2, ..., A_N$. Initially, this sequence is a permutation of $1, 2, ..., N$.

On this sequence, Snuke can perform the following operation:

• Choose $K$ consecutive elements in the sequence. Then, replace the value of each chosen element with the minimum value among the chosen elements.

Snuke would like to make all the elements in this sequence equal by repeating the operation above some number of times. Find the minimum number of operations required. It can be proved that, Under the constraints of this problem, this objective is always achievable.

Constraints

• $2 \leq K \leq N \leq 100000$
• $A_1, A_2, ..., A_N$ is a permutation of $1, 2, ..., N$.

Input

Input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $A_2$ $...$ $A_N$

Output

Print the minimum number of operations required.

Sample Input 1

4 3
2 3 1 4

Sample Output 1

2

One optimal strategy is as follows:

• In the first operation, choose the first, second and third elements. The sequence $A$ becomes $1, 1, 1, 4$.

• In the second operation, choose the second, third and fourth elements. The sequence $A$ becomes $1, 1, 1, 1$.

Sample Input 2

3 3
1 2 3

Sample Output 2

1

Sample Input 3

8 3
7 3 1 8 4 6 2 5

Sample Output 3

4

update @ 2024/3/10 17:17:35