KEYENCE Programming Contest 2019 C - Exam and Wizard
問題概要
N個の数列AとBに対し、Aの総和と総和が等しく、且つB[i]<=C[i](0<=i<=N-1)となる数列Cを構成する時のA[i]からC[i]への書き換える個数を最小化する。
解法
まず、明らかにAの総和がBの総和よりも小さい場合、Cは総和がAと同じでなければならないため、構成することができない(-1を出力)。
次に、すべてのA[i]に対し、B[i]がそれ以下であるなら、書き換える必要は当然生じない(0を出力)。
最後に、マスを書き換える個数を最小化する事を考えると、A[i]<B[i]のマスは書き換える必要がある。その為、その差を持っておき(A[i]-B[i]をdis[i]として持った)、dis[i]の中で負の数を全て足し合わせ、それをdis[i]の大きい方から埋めていくことで最小値を達成できるので、これらを実装してあげて、AC。
