目录
Description
给出 n 个数,求得 x,使 \(\frac{\sum_{i = 1} ^ {n}x + a[i] - min(a[i], 2x)} {n}\) 最小,并输出最后的最小值
State
\(1<=n<=10^5\)
\(1<=a[i]<=10^9\)
Input
3
3 1 4
Output
1.83333333333333333333
Solution
前质知识:
\(min(x, y) = \frac{x + y - |x - y|}{2}\)
\(max(x, y) = \frac{x + y + |x - y|}{2}\)
这样就可以将最小值换成绝对值了, \(\frac{\sum_{i = 1} ^ {n}x + a[i] - min(a[i], 2x)}{n} = \frac{\sum_{i = 1} ^ n a[i] + | a[i] - 2x | }{2n}\)
其中 \(a[i], 2n\) 都是固定的,只有 \(|a[i] - 2x|\) 受到 \(x\) 的影响;
使得答案最小,只有 \(|a[i] - 2x|\) 最小,而这就说明 \(2x\) 为 \(a[i]\) 的中位数,即 $x = \frac{a[mid]} {2} $
Code
const int N = 4e5 + 5;
ll n, m, _;
int i, j, k;
ll a[N];
signed main()
{
//IOS;
while(~ sd(n)){
rep(i, 1, n){
sd(a[i]);
}
sort(a + 1, a + 1 + n);
double x = a[(1 + n) >> 1] / 2.0, ans = 0;
rep(i, 1, n){
ans += a[i] + x - min((double)a[i], 2 * x);
}
pf(ans / n);
}
return 0;
}