2021-05-10 競プロチャレンジ供養会場: AtCoder Regular Contest 118 B - Village of M People 競技プログラミング AtCoder コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1196 (記事作成時点) 供養 解法 まず $B_{i} = \lfloor \frac{A_{i}M}{N} \rfloor$ とする 不足分の $D = M - \sum B_{i}$ 個について、$B_{i} \times N - A_{i} \times M $ が最も小さい $B_{i}$ を $1$ 大きくする操作を $D$ 回実施することで要素の合計を $M $ にする 実装 計算量は $O(K\mathrm{log}K)$ 公式解説 躓いた点 PriorityQueueの評価関数を複雑に作りすぎた