スキル \(2\) だけを用いて魔物を倒すことを考えましょう。この場合、必要な最小の操作回数は、 \(\max(\left\lceil \frac{\sum(A_i)}{K} \right\rceil, \max(A_i))\) です。

上記の値を最小化するためにスキル \(1\) を使用することを考えると、これは \(A_i\) が最大であるものに使用するのが最適です。よって、priority_queue などを用いて \(\sum(A_i)\) と \(\max(A_i)\) を管理しながら最大値に対する操作をシミュレーションすることで、ひとまず正しい答えを出力するプログラムを作成できますが、これでは \(K\) が小さいケースでTLEです。

この解法を素直に実装すると、スキル \(1\) を \(K\) 以上の同じ値に対して適用し続ける場面が登場します。このとき、 \(\left\lceil \frac{\sum(A_i)}{K} \right\rceil\) の値はちょうど \(1\) 減少し、\(\max(A_i)\) の値は（最後の \(1\) 回を除いて）変化しません。つまり、コストは適用回数に関する \(2\) 種類の一次関数の最大値の形として表すことができ、これが最小値を更新する可能性のあるポイントは定数個しか存在しません。

よって、スキル \(1\) を適用する時の値それぞれに関して上記のポイントを列挙し、解を更新すれば良いです。また、\(K\) 未満の値に対して適用するような回数は \(O(N)\) 回しか存在しないため、これらについては素直にシミュレーションすれば良いです。

よって、この問題は \(O(\max(A_i) + N)\) で解くことができました。