ABC101 C - Minimization

問題はこちら atcoder.jp

方針

数列 は を並び替えたものなので，題意の操作の結果は， となるほかありません。

このとき，置き換えられるべき要素は 以外の 個であり，1回の操作で最大 個の要素を置き換えることができます。

つまり，求める操作回数は，（ 以上で最小の整数）です。

操作は を含む部分から始めればよく，操作回数は数列の並びによらず一定なので，実は を受け取る必要もありません。

（簡単すぎて嘘解法かと疑いましたが，解説PDFでも同様の解法が紹介されていました。こちらには証明もついています。）

コード

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

int main(){
    int n,k;
    cin>>n>>k;

    cout<<ceil((double)(n-1)/(k-1))<<endl;
}