/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
左右方向一列に N 個のマスが並んでいます。左から i 番目のマスをマス i と呼ぶことにします。
この N 個のマスのうち、マス A_1, マス A_2, マス A_3, \dots, マス A_M の M 個のマスは青色で、それ以外のマスは白色です。(M = 0 の可能性もあり、その場合青色のマスはありません。)
あなたは一回だけ、正整数 k を一つ選んで幅 k のハンコを作ります。幅 k のハンコを一回使用すると、N 個のマスのうち連続する k マスを選び、それらを赤色に塗り替えることができます。ただしその際、その 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 を選び、3 つある白色マスを一回に一つずつ赤色に塗り替えると 3 回で目的を達成でき、最適です。
k として 2 以上を選ぶと、ハンコの使用時に k 個のマスの中に青色のマスが入っていてはいけないという制約のためにマス 2 がどうやっても赤色に塗り替えられなくなってしまいます。
入力例 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
最初から白色のマスが存在しない場合、ハンコは 1 回も使わなくてよいです。
入力例 4
1 0
出力例 4
1
M = 0 の可能性もあります。
Score : 400 points
Problem Statement
There are N squares arranged in a row from left to right. Let Square i be the i-th square from the left.
M of those squares, Square A_1, A_2, A_3, \ldots, A_M, are blue; the others are white. (M may be 0, in which case there is no blue square.)
You will choose a positive integer k just once and make a stamp with width k. In one use of a stamp with width k, you can choose k consecutive squares from the N squares and repaint them red, as long as those k squares do not contain a blue square.
At least how many uses of the stamp are needed to have no white square, with the optimal choice of k and the usage of the stamp?
Constraints
- 1 \le N \le 10^9
- 0 \le M \le 2 \times 10^5
- 1 \le A_i \le N
- A_i are pairwise distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_M
Output
Print the minimum number of uses of the stamp needed to have no white square.
Sample Input 1
5 2 1 3
Sample Output 1
3
If we choose k = 1 and repaint the three white squares one at a time, three uses are enough, which is optimal.
Choosing k = 2 or greater would make it impossible to repaint Square 2, because of the restriction that does not allow the k squares to contain a blue square.
Sample Input 2
13 3 13 3 9
Sample Output 2
6
One optimal strategy is choosing k = 2 and using the stamp as follows:
- Repaint Squares 1, 2 red.
- Repaint Squares 4, 5 red.
- Repaint Squares 5, 6 red.
- Repaint Squares 7, 8 red.
- Repaint Squares 10, 11 red.
- Repaint Squares 11, 12 red.
Note that, although the k consecutive squares chosen when using the stamp cannot contain blue squares, they can contain already red squares.
Sample Input 3
5 5 5 2 1 4 3
Sample Output 3
0
If there is no white square from the beginning, we do not have to use the stamp at all.
Sample Input 4
1 0
Sample Output 4
1
M may be 0.