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

Cho mảng arr[] và số M. Nhiệm vụ: chọn M phần tử sao cho chênh lệch 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ụ

Đầu vào: arr[] = {3, 1, 6, 9, 4}, M = 3

Đầu ra: 15

Giải thích

Chọn 4, 6, 9. Tổng = 19. Chênh lệch tuyệt đối với tổng phần còn lại (3+1=4): |19 - 4| = 15.

Phương pháp giải

Chênh lệch lớn nhất chỉ xảy ra khi chọn M số lớn nhất hoặc M số nhỏ nhất. Kiểm tra cả hai và so sánh. Sắp xếp mảng để dễ lấy M số lớn/nhỏ nhất.

Ví dụ

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

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

int main() {
    int arr[] = {3, 1, 6, 9, 4};
    int M = 3;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "Chênh lệch trọng lượng tối đa là " << maxWeightDifference(arr, N, M);
    return 0;
}

Đầu ra

Chênh lệch trọng lượng tối đa là 15