ARC099 C : Minimization(300)
作成日：2018.10.03
最終更新日：2018.10.03
問題概要
$1$から$N$までの順列である数列$\{A_i\}$に操作「連続した$K$個の要素を選び、それらの最小値で置き換える」を行う。
この数列の要素をすべて等しくするために必要な操作の最小回数を求めよ。
制約
$2 \leq K \leq N \leq 10^5$
$\{A_i\}$は$1$から$N$までの順列
考え方
数列の最小値は$1$であるから、数列の要素をすべて$1$にすることを考えれば良い。
すると操作では$1$を含む区間を選び、$1$でない要素を$1$にしていけば良いことが分かる。
1回の操作で増やせる$1$に等しい要素の数は$K-1$であるから、少なくとも$\lceil \frac{N-1}{K-1} \rceil$回の操作が必要である。
一方、以下のようするとこの最小値が達成できることが分かるから、これが答えである。
操作を逆方向に考える。
元から$1$である要素から最も遠い$1$である要素から連続した$(K-1)$個の$1$である要素を元の値に戻していくことを可能な限り繰り返す。
すると$K$個以下の連続した$1$である要素が残る。
実際には、逆操作で残った要素が1個でないならばそれらがすべて$1$になるように操作をした後、逆操作と逆順に操作を行えば良い。
ソースコード
マクロ等はこちら
int main(){
int N,K; cin >> N >> K;
repp(i,0,N){int A; cin >> A;}
cout << (N-1+K-2)/(K-1) << endl;
return 0;
}解法まとめ
答えは$\lceil \frac{N-1}{K-1} \rceil$である。(4行)