← 返回题目列表

AtCoder · abc185_d

D. 邮票

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

分数: 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.