25945: 컨테이너 재배

• toc {:toc}

문제 확인하기

풀이

Fig1 Fig2

1. 컨테이너가 많이 있는 쪽에서 적은 쪽으로 옮긴다는 것은 결국 부족한 부분의 개수를 세면 된다는 것이다.
2. 전체 개수의 평균을 통해 평균보다 작은 경우 부족한 개수를 센다.

Fig1의 평균 = 4.xx 이고 부족한 부분을 4까지 채우는 개수는 5가 된다. 처음에는 다음과 같은 방식으로 개수를 셌는데 반례가 존재했다.

4 3 3 3 9

위와 같이 입력이 주어지는 경우 평균 = 4.xx, 평균보다 작은 경우를 4에 맞춰서 채우면 움직이는 컨테이너 수는 3이다. 하지만 3개만 움직일 경우 9개가 있는 컨테이너의 수가 6이 되어 조건에 맞지 않게 된다.

결국 평균치+1 보다 높은 개수도 확인을 해주고 다른 위치로 옮겨줘야 할 필요가 있다. 때문에 평균치 +1보다 높은 컨테이너 개수와 평균치보다 적은 개수 중 개수가 더 많은 경우를 선택한다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
long long containers[1000005];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    long long n, sum = 0, res = 0;
 
    cin >> n;
 
    for(int i = 0; i < n; i++){
        cin >> containers[i];
        sum += containers[i];
    }
 
    int avg = sum / n;
 
    sum = 0;
    for(int i = 0; i < n; i++){
        if(containers[i] < avg){
            res += avg - containers[i];
        }
        else if(avg+1 < containers[i]){
            sum += containers[i] - (avg+1);
        }
    }
    if(sum > res){
        res = sum;
    }
    cout << res << endl;
 
    return 0;
}