알고리즘
BOJ 15460 My Cow Ate My Homework
굽굿
2022. 4. 20. 12:53
https://www.acmicpc.net/problem/15460
15460번: My Cow Ate My Homework
In your bovine history class, you have been given a rather long homework assignment with $N$ questions ($3 \leq N \leq 100,000$), each graded with an integer score in the range 0...10,000. As is often customary, your teacher plans to assign a final grade b
www.acmicpc.net
역순으로 하나씩 합쳐보면 전처리 없이 정답을 구할 수 있다.
소수정밀도에 대해 안다면 코드를 굉장히 짧게 줄일 수 있다.
#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;
}