← 返回题目列表

Codeforces · 1065/C

C. 使其相等

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

有一座由 $$$n$$$ 塔组成的玩具建筑。每座塔都由几个相互堆叠的立方体组成。第 $$$i$$$ 塔由 $$$h_i$$$ 立方体组成,因此它的高度为 $$$h_i$$$。

让我们在某个高度 $$$H$$$ 上定义操作切片,如下所示:对于每个塔 $$$i$$$,如果其高度大于 $$$H$$$,则删除一些顶部立方体,使塔的高度等于 $$$H$$$。一“片”的成本等于从所有塔中移除的立方体的总数。

如果切片的成本低于或等于 $$$k$$$ ($$$k \ge n$$$),我们将其命名为好切片。

计算要使所有塔具有相同高度所需的最小良好切片数。当然,总是有可能做到这一点。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le k \le 10^9$$$) — 分别是塔的数量和切片的限制。

第二行包含 $$$n$$$ 空格分隔的整数 $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 2 \cdot 10^5$$$) — 塔的初始高度。

输出

打印一个整数 - 使所有塔具有相同高度所需的最小良好切片数。

示例

输入 #1

5 5
3 1 2 2 4

输出 #1

2

输入 #2

4 5
2 3 4 5

输出 #2

2

注意

在第一个示例中,最好制作 $$$2$$$ 切片。第一个切片的高度为 $$$2$$$(其成本为 $$$3$$$),第二个切片的高度为 $$$1$$$(其成本为 $$$4$$$)。