10019번: Sabotage

https://www.acmicpc.net/problem/10019


$O(nC)$

s[i]: m[1...i]의 합

파라매트릭 서치를 하기 위해 문제를 평균이 p이하가 될 수 있는지 결정하는 문제로 바꿔보자.
즉,
(s[n]-s[i]+s[j])/(n-i+j)<=p (1<=j<i<n) 인 i, j가 존재하는지 확인하면 된다.
위 식은
s[n]-p*n+(p*i-s[i])-(p*j-s[j])<=0 과 동치이고
이는 f(x)=p*x-s[x]을 최댓값으로 만드는 x=j를 기억하면 매 i마다 s[n]-p*n+f(i)-f(j)의 최솟값을 O(1)에 찾을 수 있어서
매번 O(n)에 평균을 p이하로 만들 수 있는지 확인이 가능하다.

#include<cstdio>
const int MXN = 1e5;
int n, s[MXN + 1];
bool f(double a) {
    double maxi = a - s[1];
    for (int i = 2; i < n; i++) {
        if (s[n] - a*n + a*i - s[i] - maxi <= 0) return 1;
        if (a*i - s[i]>maxi) maxi = a*i - s[i];
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
    double low = 1, up = 1e4, mid;
    while (up - low > 1e-6) {
        mid = (low + up) / 2;
        f(mid) ? up = mid : low = mid;
    }
    printf("%.3lf", mid);
    return 0;
}