Hướng dẫn giải của Codeforces Educational 3C - Load Balacing


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.