360 笔试 交换两个数组的两个数，求两个数组和绝对值的最小

直接输出1,40%

帮同学做了，最后时间紧没写完，说下思路吧。 先算出residual=sumA-sumB，然后将B中的每一个数与A中的每一个数相减，放入数组nums（M*N维）     如果nums中有与residual相同的，直接返回0，因为换两次可以视作换一次（例如ab，bc相当于就是ac换）。 如果没有相同的，先对nums排序，找到两个数的和sumX与residual最近即可，最后结果为|sumX-residual|（这个找法也可以有优化空间）

分三种情况考虑： 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); }

暴力过了40。刚想到一个办法不知道可不可以：算出每个数组所有的两两组合得到两个n(n-1)/2长度的新数组，交换两次就变成交换一次了，然后在这两个数组里各找一个数使得这两个数的差最接近原始差值/2。楼主觉得怎样

投机取巧过了80%。。不过我知道我的方法肯定有bug

一个的时候，直接nm枚举，二个的时候，暴力枚举nn，然后去二分mm

直接输出1，40%……

哎呀，我输出0过了20就交了，当时还剩30秒，早知道试试1了。

我回想起来这个题是要求只交换两组数呢？还是就那个给的用例是交换两组数呢？我暴力也是20%，是不是我题意看错了

暴力时间复杂度是O（N^4）吧