首页 > 试题广场 >

序列最小化

[编程题]序列最小化
  • 热度指数:1833 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

有一个长度为N的序列。一开始,这个序列是1, 2, 3,... n - 1, n的一个排列。

对这个序列,可以进行如下的操作:

每次选择序列中k个连续的数字,然后用这k个数字中最小的数字替换这k个数字中的每个数字。

我们希望进行了若干次操作后,序列中的每个数字都相等。请你找出需要操作的最少次数。


输入描述:

第一行:两个数字n, k,含义如题,满足2 <= k <= n <= 105

第二行:n个数字,是1, 2, 3,...n的一个排列。



输出描述:
一个整数,表示最少的次数。
示例1

输入

2 2
2 1

输出

1
示例2

输入

4 3
1 2 3 4

输出

2

这道题你会答吗?花几分钟告诉大家答案吧!