LeetCodeWeekly238B: 1838. Frequency of the Most Frequent Element: 尺取り法 - Qiita

題意 $n$個の正の数字が与えられる。 「あなたは好きな要素を$+1$してよい」これを最大で$k$回行える。(すべて別の要素を選んでもよい) ある$x$を$y$個作りたいと思ったとき$y$の最大数はいくつか？ こう考えた 例題の通り、$[1,4,8,13]$としよう。まず、ソートする。今回の場合、すでにソートされている。 $+1$しかできないので、ある数字にそろえるとすると、その数より大きい数は小さくできない。つまり、$4$は$+1$を4回行えば$8$になれるが、$8$は操作しても$1$にも$4$にもなれない。 ここで左から順に、それまでの要素をいくつ揃えられるかを考える。例えば、13に合わせるとしよう。kが十分に大きければ$[13,13,13,13]$にできる($k$が本当に大きければ$[14,14,14,14]$などにもできるが、これはyの最大数に意味がない)。 必要な$k$が小さい方