CF63B Settlers' Training

在战略电脑游戏“Settlers II”中，玩家需要建造防御结构来扩展和保护领土。现在考虑其中一个防御建筑，此时该防御结构中正好有 $n$ 名士兵。在本题中，可以假设防御结构中的士兵数量不会增加或减少。 每位士兵都有一个军衔——一个从 $1$ 到 $k$ 的自然数。其中 $1$ 代表士兵（一等兵），$k$ 代表将军。士兵的军衔越高，战斗力越强。因此，玩家会希望下属的士兵军衔尽可能高。 提升士兵军衔需要训练。但训练并不是免费的，每次训练需要一枚金币。每次训练时，所有 $n$ 名士兵都会参加。 每次训练结束时，士兵的军衔按如下方式提升。首先将所有士兵按军衔分组，使组数尽可能少。然后，对于每个军衔低于 $k$ 的组，恰好从每组中选出一名士兵，其军衔提升一级。 已知当前所有 $n$ 名士兵的军衔。请你计算，将所有士兵提升到军衔 $k$ 需要的金币数量。

第一行包含两个整数 $n$ 和 $k$（$1\leq n,k\leq 100$），分别表示士兵数量和不同军衔的数量。 第二行包含 $n$ 个非递减排列的数字。第 $i$ 个数字 $a_{i}$ 表示防御建筑中的第 $i$ 名士兵的军衔（$1\leq i\leq n$，$1\leq a_{i}\leq k$）。

输出一个整数，表示将所有士兵提升至最高军衔所需的金币数。

在第一个样例中，士兵的军衔提升顺序如下： $1\ 2\ 2\ 3 \to 2\ 2\ 3\ 4 \to 2\ 3\ 4\ 4 \to 3\ 4\ 4\ 4 \to 4\ 4\ 4\ 4$ 因此总共需要 $4$ 次训练，即 $4$ 枚金币。 由 ChatGPT 5 翻译