c++ - 通过交换元素使数组相同

Question

有2个i / p阵列。当它们具有完全相同的数字时，它们是相同的。为了使它们相同，我们可以交换它们的元素。交换将需要费用。如果我们交换a和b元素，则cost = min(a，b)。
在使阵列相同的同时，成本应最小。
如果不可能使数组相同，则打印-1。

i/p:     
3 6 6 2  
2 7 7 3   

o/p :     
4     
   

在这里，我交换了(2,7)和(2,6)。因此，最低费用= 2 + 2 = 4。
逻辑:

制作2个将存储i / p数组元素频率的 map 。

如果aMap中的元素“a”也存在于bMap中，那么我们必须考虑a = abs(aMap中的freq(a)-bMap中的freq(a))的交换数量

如果元素的频率为“奇数”，则不可能使它们相同。

else，从两张 map 中添加总掉期并使用
成本=最小元素*总掉期

这是代码

#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int size;
        long long int cost = 0;
        cin >> size;
        bool flag = false;
        map<long long int, int> aMap;
        map<long long int, int> bMap;
        
        // storing frequency of elements of 1st input array in map
        for( int i = 0 ; i < size; i++)
        {
            long long int no;
            cin >> no;
            aMap[no]++;
        }

        // storing frequency of elements of 2nd input array in map
        for(int i = 0 ; i < size; i++)
        {
            long long int no;
            cin >> no;
            bMap[no]++;
        }

        // fetching smallest element (i.e. 1st element) from both map
        long long int firstNo = aMap.begin()->first;
        long long int secondNo = bMap.begin()->first;
        long long int smallestNo;
       
        // finding smallest element from both maps
        if(firstNo < secondNo)
            smallestNo = firstNo;
        else
            smallestNo = secondNo;

        map<long long int, int> :: iterator itr;

        // trying to find out total number of swaps we have to perform
        int totalSwapsFromA = 0;
        int totalSwapsFromB = 0;

        // trversing a map
        for(itr = aMap.begin(); itr != aMap.end(); itr++)
        {
            // if element "a" in aMap is also present in bMap, then we have to consider
            // number of swapping = abs(freq(a) in aMap - freq(a) in bMap)
            auto newItr = bMap.find(itr->first);
            if(newItr != bMap.end())
            {
                if(itr->second >= newItr->second)
                {
                    itr->second -= newItr->second;
                    newItr->second = 0;
                }
                else
                {
                    newItr->second -= itr->second;
                    itr->second = 0;   
                }                        
            }
            // if freq is "odd" then, this input is invalid as it can not be swapped
            if(itr->second & 1 )
            {
                flag = true;
                break;
            }
            else
            {
                // if freq is even, then we need to swap only for freq(a)/ 2 times
                itr->second /= 2;

                // if swapping element is smallest element then we required 1 less swap
                if(itr->first == smallestNo && itr->second != 0)
                    totalSwapsFromA += itr->second -1;
                else
                    totalSwapsFromA += itr->second;
            }
            
        }  

        // traversing bMap to check whether there any number is present which is 
        // not in aMap.
      if(!flag)
      {
        for(itr = bMap.begin(); itr != bMap.end(); itr++)
        {
            auto newItr = aMap.find(itr->first);
            if( newItr == aMap.end())
            {
                // if frew is odd , then i/p is invalid
                if(itr->second & 1)
                {
                    flag = true;
                    break;
                }
                else
                {
                    itr->second /= 2;

                    // if swapping element is smallest element then we required 1 less swap
                    if(itr->first == smallestNo && itr->second != 0)
                        totalSwapsFromB += itr->second -1;
                    else
                        totalSwapsFromB += itr->second;
                    
                }
                
            }
        } 
     }
       if( !flag )
       {   
          cost = smallestNo * (totalSwapsFromB + totalSwapsFromA);
          cout<<"cost "<<cost <<endl;
       }
       else
           cout<<"-1"<<endl;
    }
    return 0;
}
    

上面的代码没有错误，但是给出了错误的答案，没有被接受。
任何人都可以改善此代码/逻辑吗？

Answer 1

假设您有2个数组:

A: 1 5 5
B: 1 4 4

我们知道我们想将下移5并将上移4，因此我们必须选择:用5交换4(使用cost min(4, 5) = 4)或使用minimum元素获得相同的结果，进行2次交换:

A: 1 5 5   swap 1 by 4 (cost 1)
B: 1 4 4    
________
A: 4 5 5   swap 1 by 5 (cost 1)
B: 1 1 4
________
A: 4 1 5   total cost: 2
B: 5 1 4    

因此，我们每次交换都要做的问题是这个。直接交换还是使用最小元素作为枢轴交换两次更好？
简而言之，让m为两个数组中的最小元素，并且您想将i交换为j。掉期成本为

min( min(i,j), 2 * m )

因此，只需找出您需要做的所有交换，应用此公式并对结果求和即可得到答案。