この問題は \(A\) が降順ソートされていれば、\(O(N)\) で解くことができます。

\(N=M\) のケースは簡単なのでこれ以降考えないこととします。

まず、\(R:=K - \sum A\) と定義します。これは、残りの票数です。

\(i = M+1, \dots ,N\) 人目の候補者について、それらの人が必ず当選するのに必要な票数は以下の式のいずれかを満たす最大の整数 \(X\) と同じです。

• \(X=A_{M}\)
• \(\sum_{k=1}^{M} (\max(X, A_{k}) -A_{k}) + X- A_{i} -1\leq R\)

\(X\) が \(i\) に対して単調減少であることと、\(\max(X, A_{k}) =A_{k}\) を満たす \(1\leq k \leq M\) の個数が変わらない限り、\(2\) 番目の式の左辺は \(X\) の \(1\) 次関数で表されることを用いて、\(i = N,\cdots , M+1\) の順に時間計算量 \(O(N)\) で \(X\) を求めることができます。

\(1,2,\dots ,M\) 人目の候補者が必要な票数は、\(M+1\) 人目の候補者が必要な票数と同じです。

よって、全ての候補者について必要な票数が、ソートを除いて線形で求めることができました。

実装例 https://atcoder.jp/contests/abc373/submissions/58285054