BOJ 15460 My Cow Ate My Homework

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

15460번: My Cow Ate My Homework

 

역순으로 하나씩 합쳐보면 전처리 없이 정답을 구할 수 있다.
소수정밀도에 대해 안다면 코드를 굉장히 짧게 줄일 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
unsigned long long arr[100001], n, lmin, tsum;
double epsilon = 1.0e-6;
std::vector<int> v;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%llu",arr+i);
    lmin = std::min(arr[n], arr[n-1]);
    tsum = arr[n] + arr[n-1];
    double avg = double(tsum-lmin);
    v.push_back(n-2);
    for(int i=n-2;i>1;i--) {
        tsum += arr[i];
        lmin = std::min(lmin, arr[i]);
        double la = (double)(tsum - lmin) / (double)(n-i);
        
        if(std::abs(la - avg) < epsilon) {
        	v.push_back(i-1);
        }
        else if(la - avg >= epsilon){
        	avg = la;
            std::vector<int>().swap(v);
            v.push_back(i-1);
        }
        //printf("%d %d %d %d %.5f\n",i, tsum, lmin, la, n-i+1);
    }
    std::sort(v.begin(), v.end());
    for(int i : v) printf("%d\n",i);
    return 0;
}