数组交换

Bertha 。 2022-08-02 00:18 139阅读 0赞

有两个序列a,b，大小都为n,序列元素的值任意整数，无序；  
要求：通过交换a,b中的元素，使\[序列a元素的和\]与\[序列b元素的和\]之间的差最小。  
例如:     
var a=\[100,99,98,1,2, 3\];

var b=\[1, 2, 3, 4,5,40\];

// exchange_array.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<cmath>
    using namespace std;
    
    #define INFTY 2147483647
    
    int sumof(int*in, int len);
    int exchange(int*aa, int*bb, int len);
    int _tmain(int argc, _TCHAR* argv[])
    {
    	const int len = 6;
    	int a[len] = { 100, 99, 98, 1, 2, 3 };
    	int b[len] = { 1, 2, 3, 4, 5, 40 };
    	
    	int aa[6], bb[6];
    	cout << sumof(a, len) << endl;
    	cout << sumof(b, len) << endl;
    	cout << abs(sumof(a, len) - sumof(b, len))<<endl;
    	int k1 = exchange(a, b, len);
    	cout << k1 << endl;
    	int k2 = exchange(a, b, len);
    	cout << k2<<endl;
    	while (k1 > k2)
    	{
    		for (int i = 0; i < len; i++)
    		{
    			aa[i] = a[i];
    			bb[i] = b[i];
    		}
    		k1 = k2;
    		k2 = exchange(a, b, len);
    	}
    
    	for (int i = 0; i < len; i++)
    		cout << aa[i] << endl;
    	cout << k1<<endl;
    	system("pause");
    	return 0;
    }
    //求和
    int sumof(int*in, int len)
    {
    	int sum=0;
    	for (int i = 0; i < len; i++)
    		sum += in[i];
    	return sum;
    }
    //交换一次，得到当前最好的结果
    int exchange(int*aa, int*bb, int len)
    {
    	int ii = 0, jj = 0;
    	int best = INFTY;
    	
    	int re = sumof(bb, len) - sumof(aa, len);
    	if (re == 0)
    		return 0;
    	
    		for (int i = 0; i < len; i++)
    			for (int j = 0; j < len; j++)
    		{
    			int x;
    			if (re < 0)
    				x = abs((2 * (aa[i] - bb[j]) + re));
    			else
    				x = abs((2 * (bb[j] - aa[i]) + re));
    			if (x < best)
    			{
    				best = x;
    				ii = i;
    				jj = j;
    			}
    		}
    		int ss = aa[ii];
    		aa[ii] = bb[jj];
    		bb[jj] = ss;
    		return best;
    }