题解

思路

设现有评论数为 $q$、星级总和为 $p$。

做法

增加一条四星评论能让“星级总和减去评论数的三倍”增加 $1$，增加一条五星评论能使它增加 $2$；增加三星及以下的评论不可能更优。因此只需补足缺口 $d=3q-p$，若 $d\le 0$ 则答案为 $0$，否则在全部使用四星、全部使用五星、使用一条四星后再使用五星三种方案中取最小花费。任意两条四星评论都可以替换为一条五星评论，所以最优解一定属于这三种情形。

复杂度

每组数据的时间和空间复杂度均为 $O(1)$。