15460-My Cow Ate My Homework(Silver)

15460-My Cow Ate My Homework

수열 arr가 주어지고 소는 수열의 숫자를 앞에서부터 최소 1개부터 최대 n개까지 먹어서 없앨 수 있다. 그리고 없앤 뒤의 수열들 중에서 가장 작은 수 하나를 삭제한 뒤 나머지 값들의 평균(합/개수)을 구해서 그 평균의 값이 가장 크게 되도록 하려면 질문을 몇 개 먹어야 하는지를 묻고 있다.(그 개수가 여러개라면 오름차순으로 모두 출력한다)

단순 구현문제로, 루프로 1개 없애는 경우부터 n개 없애는 경우까지 모두 살펴봐서 평균값을 계산해보면 된다. 일단 평균을 구하기 위해서는 먹어치운 k개를 제외한 나머지 (k+1)~n번째에서 가장 작은 값을 제외한 나머지의 합을 구한 뒤, 개수로 나눈 값이 평균이 되고, 평균의 최대값을 저장하는 변수와 일일이 비교해서 필요에 따라 갱신해주면 된다. 여기서 n=10만이기 때문에 시간복잡도는 O(n * logn)까지만 허용될 것이다. 따라서 구간 합을 O(1)만에 구할 수 있는 누적 합 배열(sum[])을 만들고, 구간에서 가장 작은 값을 저장하는 lowest[]배열을 만들면 된다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 100009
int n,arr[SIZE],sum[SIZE],lowest[SIZE];
double seg_sum[SIZE];
vector<int> ans;
int main(){
    scanf("%d",&n);
 
    for(int i=1 ; i<=n ;i++){
        scanf("%d",&arr[i]);
    }
 
    for(int i=1 ; i<=n ; i++){
        sum[i]=sum[i-1]+arr[i];
    }
 
    lowest[n]=arr[n]; //lowest[i]=min[i,n];
    for(int i=n-1 ; i>=1 ; i--){
        lowest[i]=min(lowest[i+1],arr[i]);
    }
 
    double max_val=0;
    for(int i=2 ; i<=n-1 ; i++){
        seg_sum[i]=(double)(sum[n]-sum[i-1]-lowest[i])/(n-i);
        max_val=max(seg_sum[i],max_val);
    }
 
 
    for(int i=1 ; i<=n ; i++){
        if(max_val==seg_sum[i]){
            ans.push_back(i-1);
        }
    }
 
    for(int here:ans)
        printf("%d\n",here);
    return 0;
 
}