万维网站,seo推广技术培训,微信域名防封在线生成,课程网站建设ppt模板32. 有两个序列a,b#xff0c;大小都为n,序列元素的值任意整数#xff0c;无序; 要求:通过交换a,b中的元素#xff0c;使[序列a元素的和]与[序列b元素的和]之间的差最小。 当前数组a和数组b的和之差为 A sum(a) - sum(b) a的第i个元素和b的第j个元素交换后#xff0c;a和…32. 有两个序列a,b大小都为n,序列元素的值任意整数无序; 要求:通过交换a,b中的元素使[序列a元素的和]与[序列b元素的和]之间的差最小。 当前数组a和数组b的和之差为 A sum(a) - sum(b) a的第i个元素和b的第j个元素交换后a和b的和之差为 A sum(a) - a[i] b[j] - sum(b)- b[j] a[i]) sum(a) - sum(b) - 2 (a[i] - b[j]) A - 2 (a[i] - b[j]) 设x a[i] - b[j] |A| - |A| |A| - |A-2x| 假设A 0, 当x在(0,A)之间时做这样的交换才能使得交换后的a和b的和之差变小x越接近A/2效果越好, 如果找不到在(0,A)之间的x则当前的a和b就是答案。 #includeiostream
using namespace std;
class RunClass{public:void BalanceArray(int array1[],int array2[],int n1,int n2);private:int sum(int array[],int n);
};int RunClass::sum(int array[],int n){//计算数组和int sum0;for(int i0;in;i){sumarray[i];}return sum;
}void RunClass::BalanceArray(int array1[],int array2[],int n1,int n2){if(n1!n2) return;int *arraynew int[n1];int sumValuesum(array1,n1)-sum(array2,n2);if(sumValue0){//比较两个数组和的大小让array1array2sumValue-sumValue;arrayarray1;array1array2;array2array;}bool ifCycletrue;//控制循环while(ifCycle){ifCyclefalse;for(int i0;in1;i)for(int j0;jn2;j){int itemValuearray1[i]-array2[j];if(itemValuesumValueitemValue0){//如果存在交换后能使差变小的a,bifCycletrue;int temparray1[i];//交换它们array1[i]array2[j];array2[j]temp;sumValue-2*itemValue;//校准A上面推的公式}}}
}int main(){int array1[]{1,2,3,4,5,6,7,81,9,90};int array2[]{3,9,2,8,7,1,6,11,13,7};RunClass a;a.BalanceArray(array1,array2,10,10);for(int i0;i10;i)coutarray1[i] ;coutendl;for(int i0;i10;i)coutarray2[i] ;coutendl;return 0;
} 转载于:https://www.cnblogs.com/wabi87547568/p/5275827.html
