C. Load Balancing

Math, Average


출처: Codeforces C. Load Balancing

SOL)

input으로 들어온 배열을 정렬한 후 총합 s를 얻는다.
그리고 배열의 값의 평균을 구한다.
이 평균 값은 소수점이 아니라 정수형으로 내림이 된다.
분명한 것은 모든 배열의 원소들의 값은 평균 또는 평균 + 1이
되어야한다는 것이다.
평균 + 1이 되는 원소들은 remain = s % n개 만큼 있고
뒤에서 부터 1씩 평균 + 1을 넣어주며 된다.




[-] Collapse

#include<stdio.h>
#include<algorithm>
using namespace std;

int arr[100010];
int goal[100010];
int n, ans, avr, rem;
int main(){
    //freopen("input.txt", "r", stdin);

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        avr += arr[i];
    }
    rem = avr%n;
    avr /= n;

    sort(arr, arr + n);

    for (int i = 0; i < n; i++) goal[i] = avr;

    for (int i = n - 1; i >= 0; i--){
        if (rem == 0) break;
        goal[i]++;
        rem--;
    }

    for (int i = 0; i < n; i++){
        if (arr[i] > goal[i])
            ans += arr[i] - goal[i];
    }

    printf("%d", ans);

    return 0;
}