数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究C++ 中的最大重量差
在这个问题中，我们给定一个数组 arr[] 和一个数 M。我们的任务是创建一个程序，用 C++ 计算最大重量差。
问题表述
我们将从数组中找 M 个元素，使它们之和与其余元素之和的绝对差最大。
让我们举个例子来理解这个问题：
输入：arr[] = {3, 1, 6, 9, 4} M = 3
输出：15: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
更新于：2020-10-09
171 次浏览
广告