問題概要
問題ページ
-
-
D - Stamp
問題ページへ移動する
問題文
左右方向一列に 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 は互いに異なる
- 入力は全て整数
問題の考察
ACコード
import sys
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, m = list(map(int, input().rstrip('\n').split()))
if m == 0:
print(1)
else:
a = sorted(list(map(int, input().rstrip('\n').split())))
if a[0] != 1:
a = [0] + a
if a[-1] != n:
a += [n + 1]
dif = []
mn = 10 ** 20
for i in range(1, len(a)):
dif_v = a[i] - a[i - 1] - 1
if dif_v != 0:
mn = min(mn, dif_v)
dif.append(dif_v)
if mn == 10 ** 20:
print(0)
else:
total = 0
for v in dif:
total += (v + mn - 1) // mn
print(total)
if __name__ == '__main__':
solve()