Editorial for Codeforces Educational 3C - Load Balacing


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gọi ~S~ là tổng các phần tử trong mảng. Nếu ~S~ chia hết cho ~n~ thì dãy cân bằng gồm ~n~ phần tử ~\frac{S}{n}~. Trong trường hợp này, hiệu số giữa tải lớn nhất và tải nhỏ nhất là ~0~.

Dễ thấy rằng trong tất cả các trường hợp khác, câu trả lời lớn hơn ~0~. Mặt khác, mảng gồm ~S~ ~mod~ ~n~ số ~[\frac{S}{n}]~ và mảng gồm ~n - S~ ~mod~ ~n~ số ~[\frac{S}{n}]~ thì luôn cân bằng với hiệu số là ~1~.

Gọi ~b~ là mảng cân bằng với ~a~. Để có được mảng ~b~, chúng ta hãy sắp xếp mảng ~a~ theo thứ tự giảm dần. Việc tiếp theo, ta cần phải tăng một số phần tử và giảm một số phần tử khác. Trong một giây, chúng ta có thể tăng một phần tử và giảm một phần tử khác nên ta có công thức: ~ \frac{\sum _{i=1}^{n} |a_i-b_i|}{2}~

Độ phức tạp: ~O(n \log_2 n)~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;
int const N = 1e5 + 11;
int a[N], n, sum, ans;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        sum += a[i];
    }

    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
        if(i <= n - sum % n)
            ans += abs(sum / n - a[i]);
        else
            ans += abs(a[i] - (sum / n + 1));
    cout << ans / 2;
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.