AT_abc185_d [ABC185D] Stamp

题目描述

在左右方向上有 $N$ 个格子排成一列。我们将从左起第 $i$ 个格子称为格子 $i$。
在这 $N$ 个格子中，格子 $A_1$、格子 $A_2$、格子 $A_3$、$\dots$、格子 $A_M$ 这 $M$ 个格子是蓝色的，其余格子是白色的。（$M = 0$ 也是可能的，这种情况下没有蓝色格子。）
你只能选择一次，选定一个正整数 $k$，制作一个宽度为 $k$ 的印章。每次使用宽度为 $k$ 的印章时，可以选择 $N$ 个格子中连续的 $k$ 个格子，并将它们涂成红色。但此时，这 $k$ 个格子中不能包含蓝色格子。
请问，合理选择 $k$ 和印章的使用方式后，最少需要使用多少次印章，才能使得不存在白色格子的状态？

输入格式

输入以以下格式从标准输入读入。

$N$ $M$ $A_1\ \hspace{7pt}\ A_2\ \hspace{7pt}\ A_3\ \hspace{5pt}\ \dots\ \hspace{5pt}\ A_M$

输出格式

输出一个整数，表示最少需要使用多少次印章，才能使所有白色格子都被涂成红色。

输入输出样例 #1

输入 #1

5 2
1 3

输出 #1

3

输入输出样例 #2

输入 #2

13 3
13 3 9

输出 #2

6

输入输出样例 #3

输入 #3

5 5
5 2 1 4 3

输出 #3

0

输入输出样例 #4

输入 #4

1 0

输出 #4

1

说明/提示

限制条件

• $1 \leq N \leq 10^9$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $A_i$ 互不相同
• 所有输入均为整数

样例解释 1

选择 $k=1$，将 3 个白色格子分别用印章一次涂成红色，共需 3 次，为最优解。如果选择 $k \geq 2$，由于印章不能覆盖蓝色格子，格子 2 无论如何都无法被涂成红色。

样例解释 2

例如选择 $k=2$，可以如下使用印章达到最优：

• 将格子 $1,2$ 涂成红色
• 将格子 $4,5$ 涂成红色
• 将格子 $5,6$ 涂成红色
• 将格子 $7,8$ 涂成红色
• 将格子 $10,11$ 涂成红色
• 将格子 $11,12$ 涂成红色 印章每次选择的连续 $k$ 个格子不能包含蓝色格子，但可以包含已经变成红色的格子。

样例解释 3

如果一开始就不存在白色格子，则一次印章都不需要使用。

样例解释 4

$M=0$ 也是可能的。

由 ChatGPT 4.1 翻译