Voldemort's blog

Voldemort's blog

我好菜啊

题解 CF991B 【Getting an A】

posted on 2020-05-31 11:34:08 | under 题解 |

题解 CF991B 【Getting an A】

Solution

题目中问你最少要做几次试验,所以我们就可以考虑贪心,每一次我们都改那个做的最差的,这样子平均分上来的就最快。
那么怎样才可以让平均分四舍五入到满分呢?
我们列个不等式:
$$\dfrac{s}{n} \ge 4.5$$
$$\therefore s\ge 4.5n$$
$$\therefore 2s\ge 9n$$

所以我们只要让总分 $s$ 满足上面的不等式就好了。
由于每次改分都会产生一个满分,所以我们通过维护一个来取得最小值。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 109;

int a[N],n,s,cnt;

priority_queue<int,vector<int>,greater<int> > q;

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        q.push(a[i]);
        s += a[i];
    }
    while(2 * s < 9 * n) {
        cnt++;
        s += (5 - q.top());
        q.pop();q.push(5);
    }
    printf("%d\n",cnt);
    return 0;
}