Voldemort's blog

Voldemort's blog

我好菜啊

题解 CF810A 【Straight «A»】

posted on 2020-05-24 11:45:39 | under 题解 |

题解 CF810A 【Straight «A»】

Solution

这道题目我们可以用不等式来解决,下面写出数学推导。


设要加上 $m$ 个 $k$ 能使平均数四舍五入后等于 $k$。
由题意得:
$$(k+0.4)(n+m)\ge \sum\limits_{i=1}^n a_i+mk\ge (k-0.5)(n+m)$$
因为我们要求最小值,所以我们只需要解不等式:
$$\sum\limits_{i=1}^n a_i+mk\ge (k-0.5)(n+m)$$
$$\sum\limits_{i=1}^n a_i\ge nk-0.5n-0.5m$$
$$\sum\limits_{i=1}^n a_i+0.5n+0.5m-nk\ge 0$$
$$2\times\sum\limits_{i=1}^n a_i+n+m-2nk\ge 0$$
$$m\ge 2nk-n-2\times\sum\limits_{i=1}^n a_i$$

所以说,如果我们要取 $m$ 的最小值,那么 $m=2nk-n-2\times\sum\limits_{i=0}^n a_i$。
但是注意,我们有一个默认条件: $m\ge 0$,所以当解出的值小于0时,要把它换成0。

Code

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

const int N = 109;

int n,k,m,s;
int a[N];

int main() {
    scanf("%d %d",&n,&k);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        s += a[i];
    }
    m = 2 * n * k - n - s * 2;
    if(m <= 0) m = 0;
    printf("%d\n",m);
    return 0;
}