ความแตกต่างน้ำหนักสูงสุด (Maximum Weight Difference) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และจำนวน M ภารกิจคือการสร้างโปรแกรมคำนวณ Maximum Weight Difference ใน C++

ข้อความปัญหา

เราจะหา M สมาชิกจากอาร์เรย์ทำให้ความต่างสัมบูรณ์ระหว่างผลรวมของ M สมาชิกนั้นกับผลรวมของสมาชิกที่เหลือเป็นค่าสูงสุด

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต: arr[] = {3, 1, 6, 9, 4}, M = 3

เอาต์พุต: 15

คำอธิบาย

เราพิจารณา 4, 6, 9 ผลรวมคือ 19 ความต่างสัมบูรณ์กับผลรวมของตัวเลขที่เหลือคือ |19 - 4| = 15

แนวทางแก้ปัญหา

วิธีแก้ปัญหานี้อิงจากข้อเท็จจริงที่ว่าความต่างสูงสุดจะเป็นไปได้ก็ต่อเมื่อเราเลือก M ตัวที่มากที่สุด หรือ M ตัวที่น้อยที่สุด เราต้องตรวจสอบทั้งสองกรณีและเปรียบเทียบความต่างสัมบูรณ์เพื่อหาผลลัพธ์สุดท้าย เพื่อให้ง่ายต่อการหา M ตัวมากที่สุด/น้อยที่สุด เราจะเรียงลำดับอาร์เรย์ก่อนแล้วค่อยคำนวณกับ K ตัวมากที่สุดและน้อยที่สุด

ตัวอย่างโค้ด

#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 << "The maximum weight difference is " << maxWeightDifference(arr, N, M);
    return 0;
}

ผลลัพธ์

The maximum weight difference is 15