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

Trong bài toán này, chúng ta được cung cấp một mảng arr [] và một số M. Nhiệm vụ của chúng ta là tạo một chương trình để tính Chênh lệch Trọng số Tối đa trong C ++.

Tuyên bố vấn đề

Chúng ta sẽ tìm M phần tử từ mảng sao cho hiệu số tuyệt đối giữa tổng và tổng của các phần tử còn lại là lớn nhất.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Bỏ qua :15

Giải thích

Chúng ta sẽ xem xét 4,6,9. Tổng là 19. Chênh lệch tuyệt đối với các số còn lại của sumof là

| 19 - 4 | =15

Phương pháp tiếp cận giải pháp

Giải pháp cho vấn đề dựa trên thực tế là hiệu số lớn nhất chỉ có thể có trong trường hợp M số lớn nhất hoặc M số nhỏ nhất.Và chúng ta cần kiểm tra cả hai điều kiện và so sánh sự khác biệt tuyệt đối để tìm ra kết quả cuối cùng. Để dễ dàng hơn trong quá trình tìm M số lớn nhất / nhỏ nhất, chúng ta sẽ sắp xếp mảng và sau đó thực hiện các phép tính trên K số lớn nhất và 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<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
   return 0;
}

Đầu ra

The maximum weight difference is 15