1557-A, *800

Problem - 1557A - Codeforces

문제

• $n(2\leq n \leq 10^{5})$개의 수를 공집합이 아닌 2개의 집합으로 나눈다
• 각각의 집합 평균의 합을 생각할때 최대는 얼마인가?

 

$O(n)$

let
$\mathrm{S_{a}=\sum_{i=1}^{a}arrray [i],\ S_{r} = \sum_{i=a+1}^{n}array[i],\ 1\leq a \leq n-1}$
Note that array arranged arbitrary

$$\begin{align*}
\text{Want} &= \frac{S_{a}}{a}+\frac{S_r}{n-a}\\
&=\frac{(n-a)S_{a}+aS_{r}}{a(n-a)}
\end{align*}$$

n은 상수이므로 구하는 값이 최대가 되는 $a$는 $\mathrm{either\ 1\ or\ n-1}$
$a=1$이라 두고 식을 다시 정리하면
$$\text{Want} = \frac{(n-1)S_{1}+S_{r}}{(n-1)}$$

$n-1 \geq 1$이므로 $S_{1}$이 배열의 최대값이 되면 구하고자 하는 값이 최대이다

c++

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    ll tmp;
    cout << fixed << setprecision(10);
    while(t--){
        cin >> n;
        ll sum = 0;
        ll maxval = -1e9 -1;
        loop(i, n){
            cin >> tmp;
            sum += tmp;
            if(tmp > maxval) maxval = tmp;
        }
 
        cout << (double)(sum-maxval)/(n-1)+maxval << endl;
 
    }
 
    return 0;
}cs

import sys
 
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, sys.stdin.readline().split()))
    s = sum(l)
    m = max(l)
    print(m+(s-m)/(n-1))cs