分三种情况考虑:
1.不需要交换:即当前sumA 与sumB相同,return0
2.交换一个元素:算出dis = abs(sumA - sumB) / 2;从A数组和B数组分别找到两个元素,使这两个元素的差值最接近于dis,即交换这两个元素就可以使A,B最接近,将交换后的数组和差值记录下来;
3.交换两个元素:构造新数组C,D;C为A数组任意两元素之和,D为B数组任意两元素之和;然后从数组C,D中找到两元素,使这两个元素差值最接近于dis,即交换C,D两个元素可使得A,B最接近。将交换后的数组差值记录下来。新的求和使用:newSumA = sumA + D[j] - C[i]; newSumB = sumB + C[i] - D[j]
最后将2,3中较小的输出即可。
#include "bits/stdc++.h"
using namespace std;
int GetMinDisByChange(vector<int> &A, vector<int>&B);
int ComputeMinDis(vector<int> &A, vector<int> &B, const int &threshold, const int &sumA, const int &sumB);
int main(){
/*
4
1 3 7 9
3
2 10 12*/
int n, m;
cin >> n;
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];
cin >> m;
vector<int>B(m);
for (int i = 0; i < m; i++) cin >> B[i];
cout << GetMinDisByChange(A, B) << endl;
return 0;
}
int ComputeMinDis(vector<int> &A, vector<int> &B, const int &threshold, const int &sumA, const int &sumB){
int tDis = INT_MAX;
int tId_i = 0, tId_j = 0;
for (int i = 0; i < A.size(); i++)
{
for (int j = 0; j < B.size(); j++)
{
if (sumA > sumB && A[i] > B[j] ||
sumA < sumB && A[i] < B[j])
{
int Dis = abs(A[i] - B[j]);
if (Dis && abs(Dis - threshold) < tDis)
{
tDis = abs(Dis - threshold);
tId_i = i;
tId_j = j;
}
}
}
}
tDis = abs(sumA + B[tId_j] - A[tId_i] - (sumB + A[tId_i] - B[tId_j]));
return tDis;
}
int GetMinDisByChange(vector<int> &A, vector<int>&B){
int sumA, sumB;
const int MaxChange = 2;
int ChangeCount = 0;
sumA = 0;
sumB = 0;
for (int i = 0; i < A.size(); i++) sumA += A[i];
for (int i = 0; i < B.size(); i++) sumB += B[i];
int initialDis = abs(sumA - sumB);
int MinDis = initialDis;
if (initialDis == 0)
{
return 0;
}
vector<int> C;
vector<int> D;
for (int i = 0; i < A.size(); i++)
for (int j = i + 1; j < A.size(); j++)
C.push_back(A[i] + A[j]);
for (int i = 0; i < B.size(); i++)
for (int j = i + 1; j < B.size(); j++)
D.push_back(B[i] + B[j]);
//Swap One time
int DisBySwap1 = ComputeMinDis(A, B, initialDis / 2, sumA, sumB);
//swap Two times
int DisBySwap2 = ComputeMinDis(C, D, initialDis / 2, sumA, sumB);
return min(DisBySwap1, DisBySwap2);
}