# 對兩個數組的最小乘積之和進行重新排列 > 原文： [https://www.geeksforgeeks.org/de-arrangements-for-minimum-product-sum-of-two-arrays/](https://www.geeksforgeeks.org/de-arrangements-for-minimum-product-sum-of-two-arrays/) 給定兩個大小為 n 的數組 A []和 B []。 我們需要首先對任何數組進行置換，以使對的乘積之和（每對 1 個元素）最小。 也就是說，所有 i 的 **SUM（Ai * Bi）最小。 與置換數組相比，我們還需要計算原始數組中存在的解排列數。** 例子： ``` Input : A[] = {4, 3, 2}, B[] = {7, 12, 5} Output : 3 Explanation : A[] = {4, 3, 2} and B[] = {5, 7, 12} results in minimum product sum. B[] = {7, 12, 5} is 3-position different from new B[]. Input : A[] = {4, 3, 2}, B[] = { 1, 2, 3} Output : 0 Explanation : A[] = {4, 3, 2} and B[] = {1, 2, 3} results in minimum product sum. B[] = {1, 2, 3} is exactly same as new one. ``` 從兩個數組中找到最小乘積之和的想法是對兩個數組中的一個以遞增方式進行排序，而另一個以遞減方式進行排序。 這些類型的數組將始終產生最小的對乘積之和。 對兩個數組進行排序將得出對值，即 A 中的哪個元素與 B []中的哪個元素配對。 在那之后，計算從原始數組的重新排列。 **算法**： 1. 復制兩個數組。 2. 將 copy_A []升序排列，將 copy_B []降序排列。 3. 遍歷所有 Ai，在 copy_A []中找到 Ai 作為 copy_A [j]，然后 檢查 copy_B [j] == B [i]。 如果不相等，則增加計數。 4. 返回計數值。 那將是我們的答案。 ``` // CPP program to count de-arrangements for? // minimum product. #include<bits/stdc++.h> using namespace std; // function for finding de-arrangement int findDearrange (int A[], int B[], int n) { ????// create copy of array ????vector <int> copy_A (A, A+n); ????vector <int> copy_B (B, B+n); ????// sort array in inc & dec way ????sort(copy_A.begin(), copy_A.end()); ????sort(copy_B.begin(), copy_B.end(),greater<int>()); ????// count no. of de arrangements ????int count = 0; ????for (int i=0; i<n;i++) ????{ ?????????vector<int>::iterator itA; ?????????// find position of A[i] in sorted array ?????????itA = lower_bound(copy_A.begin(),? ???????????????????????????copy_A.end(), A[i]); ?????????// check whether B[i] is same as required or not ?????????if (B[i] != copy_B[itA-copy_A.begin()]) ??????????????count++; ????} ????// return count ????return count; } // driver function int main() { ????int A[] = {1, 2, 3, 4}; ????int B[] = {6, 3, 4, 5}; ????int n = sizeof(A) /sizeof(A[0]);; ????cout << findDearrange(A,B,n); ????return 0; }? ``` 輸出： ``` 2 ``` * * * * * *