分数: 400 点
问题陈述
有 N 方块从左到右排成一排。让广场 i 是 i从左边算起第一个方格。
M 那些正方形,正方形 A_1, A_2, A_3, \ldots, A_M,为蓝色;其他人都是白色的。 (M 可能是 0,在这种情况下没有蓝色方块。)
您将选择一个正整数 k 只需一次并制作宽度印章 k。在一次使用具有宽度的印章 k,您可以选择 k 连续的方块 N 方块并将它们重新涂成红色,只要那些 k 方块不包含蓝色方块。
至少需要使用多少次印章才能没有白色方块,最优选择为 k 以及印章的用途?
约束
- 1 \le N \le 10^9
- 0 \le M \le 2 \times 10^5
- 1 \le A_i \le N
- A_i 成对不同。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_M
输出
打印没有白色方块所需的印章的最少使用次数。
示例输入 1
5 2 1 3
示例输出 1
3
如果我们选择 k = 1 并一次重新绘制三个白色方块,使用三次就足够了,这是最佳选择。
选择 k = 2 或更高版本将无法重新绘制 Square 2,由于不允许 k 方块包含一个蓝色方块。
示例输入 2
13 3 13 3 9
示例输出 2
6
一种最佳策略是选择 k = 2 并按如下方式使用印章:
- 重新绘制方块 1, 2 红色。
- 重新绘制方块 4, 5 红色。
- 重新绘制方块 5, 6 红色。
- 重新绘制方块 7, 8 红色。
- 重新绘制方块 10, 11 红色。
- 重新绘制方块 11, 12 红色。
请注意,虽然 k 使用图章时选择的连续方块不能包含蓝色方块,它们可以包含已经是红色的方块。
示例输入 3
5 5 5 2 1 4 3
示例输出 3
0
如果从一开始就没有白色方块,我们就根本不需要使用图章。
示例输入 4
1 0
示例输出 4
1
M 可能是 0.