問題概要

左右方向一列に $N$ 個のマスが並んでいます。

この $N$ 個のマスのうち、マス $A_{1}, \dots, A_{M}$ の $M$ 個のマスは青色で、それ以外のマスは白色です。

あなたは一回だけ、正整数 $K$ を一つ選んで幅 $K$ のハンコを作ります。幅 $K$ のハンコを一回使用すると、 $N$ 個のマスのうち連続する $k$ マスを選び、それらを赤色に塗り替えることができます。ただしその際、その $K$ 個のマスの中に青色のマスが入っていてはなりません。

$K$ とハンコの使用方法をうまく決めた時、最小で何回ハンコを使用すれば、白色のマスが存在しない状態にすることができるでしょうか。

制約

$1 \le N \le 10^{9}$
$0 \le M \le 2 \times 10^{5}$

考えたこと

下図のように、

白いところの塊に分けて
その長さの最小値を $K$ とする (これより長いと青マスに被ってしまう)

というふうにして、

白マスにスタンプを押していく

とすれば OK。

実装するときには、さらに下図のように、両端に青いマスを追加して考えるとわかりやすくなる。こういうのを「番兵」といったりする。

あと、青いマスが連続しているところを「長さ 0 の白塊」として処理しないように注意！！！　「長さ 0 の白塊」は除外して考えないといけない！！！

コーナーケース

以下のケースがちょっと怖い

全部が「青」
「青」が 1 個もない

実装次第だけど、これらは気にしなくてもいいようにできる。下の実装では、全部が「青」という場合は、ベクトル v が空になるだけで答えは結局 0 になる。

「青」が 1 個もないというケースは、番兵さえ入れておけば関係ない。

コード

計算量は $A$ を小さい順に並び替える必要性から、 $O(N \log N)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> A(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    sort(A.begin(), A.end());

    // 番兵追加
    A.insert(A.begin(), 0);
    A.push_back(N+1);

    // 白塊に分解 (同時に最小値も求める)
    vector<long long> v;
    long long K = N;
    for (int i = 0; i+1 < A.size(); ++i) {
        long long len = A[i+1] - A[i] - 1;
        if (len > 0) {
            v.push_back(len);
            K = min(K, len);
        }
    }

    long long res = 0;
    for (auto len : v) res += (len + K - 1) / K;
    cout << res << endl;
}