2020牛客寒假算法基础集训营4 - G 音乐鉴赏-全概率公式

题目链接：https://ac.nowcoder.com/acm/contest/3005/G
题目大意：

思路：
每个人的分数为：$a[i]*(1-x)+x*y$a[i]∗(1−x)+x∗y
要使：$a[i]*(1-x)+x*y\geq90$a[i]∗(1−x)+x∗y≥90
就是：$y\geq\frac{90-a[i]*(1-x)}{x}$y≥x90−a[i]∗(1−x)​
因为 $y\in[0, 90]$y∈[0,90]
所以：$a[i]*(1-x)+x*y\geq90$a[i]∗(1−x)+x∗y≥90的概率：
$\frac{90-\frac{90-a[i]*(1-x)}{x}}{90}$9090−x90−a[i]∗(1−x)​​
化简得：
$\frac{(a[i]-90)(1-x)}{90x}$90x(a[i]−90)(1−x)​
根据全概率公式：
$p=\frac{(a[1]-90)(1-x)}{90x}*\frac{1}{n}+\frac{(a[2]-90)(1-x)}{90x}*\frac{1}{n}+...+\frac{(a[n]-90)(1-x)}{90x}*\frac{1}{n}$p=90x(a[1]−90)(1−x)​∗n1​+90x(a[2]−90)(1−x)​∗n1​+...+90x(a[n]−90)(1−x)​∗n1​
化简：
$p=\sum_{i=1}^n\frac{(a[i]-90)(1-x)}{90xn}$p=i=1∑n​90xn(a[i]−90)(1−x)​
因为：$p=0.1$p=0.1
所以：$\sum_{i=1}^n\frac{(a[i]-90)(1-x)}{90xn}=0.1$i=1∑n​90xn(a[i]−90)(1−x)​=0.1
这里就可以用二分了。
可以化简到最后：
$x=\frac{\sum_{i=1}^n(a[i]-90)}{9n+\sum_{i=1}^n(a[i]-90)}$x=9n+∑i=1n​(a[i]−90)∑i=1n​(a[i]−90)​

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

int a[100005];
int main(){
    int n, s=0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        s+=(a[i]-90);
    }
    printf("%.2f%%\n", 100.0*s/(9*n+s));

    return 0;
}