Chênh lệch trọng lượng tối đa trong C++

Mô tả bài toán

Cho mảng arr[] và số M. Chọn M phần tử sao cho hiệu tuyệt đối giữa tổng M phần tử đó và tổng các phần tử còn lại là lớn nhất.

Ví dụ: arr = {3,1,6,9,4}, M=3 → chọn {4,6,9} tổng=19, hiệu |19-4|=15.

Giải pháp

Hiệu lớn nhất đạt được khi chọn M phần tử lớn nhất hoặc M phần tử nhỏ nhất. Sắp xếp mảng, tính hiệu cho cả hai trường hợp, lấy max.

Ví dụ minh họa (C++)

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

int maxWeightDifference(int arr[], int N, int M) {
    sort(arr, arr+N);
    int sumMin = 0, sumMax = 0, total = 0;
    for (int i = 0; i < N; i++) {
        total += arr[i];
        if (i < M) sumMin += arr[i];
        if (i >= N-M) sumMax += arr[i];
    }
    int diff1 = abs(sumMax - (total - sumMax));
    int diff2 = abs(sumMin - (total - sumMin));
    return max(diff1, diff2);
}

int main() {
    int arr[] = {3,1,6,9,4};
    int M = 3, N = 5;
    cout << "Maximum weight difference is " << maxWeightDifference(arr, N, M);
    return 0;
}

Đầu ra

Maximum weight difference is 15