106AC - Minimization

ABC101-C (300 points)

問題

長さ の数列 がある. ただし は を並び替えたもの.

• 個の連続した要素を選び, 選んだ要素それぞれの値を, 選んだ要素の中の最小値で置き換える.

という操作を繰り返して, 数列の要素を全て等しくするとき, 必要な操作の回数の最小値を求める.

• 

方針

• をを含む区間を選択するとき, その区間の数は必ず に置き換えられる→数列の最終型は全て の数列.
• 一回の操作で 個の要素を にできる.
• 初期状態で でない要素は 個.
• 貪欲に区間を選んでいくとして, 必要な操作の回数は
• 配列の中身はどうでもいい (!?

import math
 
# input
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
ans = math.ceil((N - 1) / (K - 1))
 
print(ans)