Cân bằng mảng chỉ dùng các phần tử mảng trong C++

Cho mảng arr[] gồm n phần tử. Nhiệm vụ là đếm số phép toán (cộng/trừ) tối thiểu để làm cho tất cả các phần tử của mảng bằng nhau, chỉ được sử dụng giá trị từ các phần tử trong mảng (tức là chuyển giá trị từ phần tử này sang phần tử kia). Tổng giá trị mảng không đổi.

Ví dụ minh họa

Đầu vào: arr[] = {4, 0, 3, 1, 2}

Đầu ra: 3

Giải thích: Giá trị trung bình = (4+0+3+1+2)/5 = 2. Cần chuyển giá trị để mọi phần tử thành 2.

Phương pháp giải

1. Tính tổng mảng sum. Nếu sum % n != 0 => Không thể cân bằng (trả về -1).
2. Giá trị mục tiêu avg = sum / n.
3. Số phép toán tối thiểu = (Tổng |arr[i] - avg|) / 2. (Vì mỗi phép chuyển đổi giảm độ chênh lệch 2 đơn vị: trừ 1 ở đâu, cộng 1 ở đâu).

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

int calcEqualisedOperations(int arr[], int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];

    if (sum % n != 0) return -1; // Không chia hết

    int avg = sum / n;
    long long operations = 0;
    for (int i = 0; i < n; i++) {
        operations += abs(arr[i] - avg);
    }
    return operations / 2; // Mỗi phép toán xử lý 2 đơn vị chênh lệch
}

int main() {
    int arr[] = { 5, 3, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = calcEqualisedOperations(arr, n);
    if (res == -1)
        cout << "Khong the can bang mang";
    else
        cout << "So phep toan can thiet: " << res;
    return 0;
}

Đầu ra

So phep toan can thiet: 2