[BOJ 17594] Stop Counting!

문제는 여기에서 확인 가능하다.

---

수열이 주어졌을때 그 수열의 연속부분수열을 제외한 나머지 수 들의 평균을 최대화하는 문제이다.

 

제외할 연속부분수열을 기준으로 왼쪽 수열의 평균을 $X$, 크기를 $a$라 하고, 오른쪽 수열의 평균을 $Y$, 크기를 $b$라 한뒤, 일반성을 잃지 않고 $X \geq Y$라 하자. 그러면 다음 부등식이 성립한다. 

$$\frac{aX + bY}{a+b} \leq \frac{aX + bX}{a+b} = \frac{a+b}{a+b}X = X$$

 

따라서 평균을 최대화 하는 수열은 index가 $0$에서 시작하는 연속부분수열이거나, $n-1$에서 끝나는 연속부분수열이다.

#include<bits/stdc++.h>
 
using namespace std;
 
using lld = long long int;
using lf = long double;
using uint = unsigned int;
using ulld = unsigned long long int;
using pii = pair<int, int>;
using pll = pair<lld, lld>;
 
 
int N;
lld a[1000005];
double rst;
double sum;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(9);
    cout << fixed;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> a[i];
 
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        sum += a[i];
        cnt ++;
        rst = max((double)sum/cnt, rst);
    }
    sum = 0;
    cnt = 0;
    for (int i = N-1; i >= 0; i--) {
        sum += a[i];
        cnt ++;
        rst = max((double)sum/cnt, rst);
    }
    cout << rst;
    return 0;
}