提问者:小点点

通过交换元素使数组相同


有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。

逻辑:

使I/P数组的2个频率数组。
如果元素%2!的频率=0,则无法使它们相同。
否则,将两个数组中最小的元素与其他元素交换。

这是代码

#include<iostream>
#include<algorithm>

using namespace std;
#define N 2000002

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int size;
        cin >> size;
        
        int value = 0; 
        int a[size];
        int b[size];
        bool flag = false;

        int aHash[N] = {0};
        int bHash[N] = {0};
      

        for(int i = 0; i < size; i++)
        {
            cin >> a[i];
            aHash[a[i]]++;
        }

        for( int i = 0 ; i < size; i++)
        {
            cin >> b[i];
            bHash[b[i]]++;
        }

        sort(a, a + size);
        sort(b, b + size);
        int smallerElement = 0;

        // Finding smallest elements from both array
        if(a[0] <= b[0])
            smallerElement = a[0];
        else
            smallerElement = b[0];
            
        int total = 0;
    // updating the ahash and bhash array such that we will understand which value 
    // we have to swap

        for( int i = 0; i < size; i++)
        {
            // If aHash[a[i]] == bHash[a[i]] then no need to swap a[i] value
            // so make it zero. 
            if(aHash[a[i]] == bHash[a[i]])
            {
                aHash[a[i]] = 0;
                bHash[a[i]] = 0;
            }
            else
            {
                // if aHash[a[i]] > bHash[a[i]] , update aHash[a[i]] and make 
                // bHash[a[i]] = 0. If aHash[a[i]] % 2 != 0 means it can not be 
                // swapped. Such array is not possible.
                if(aHash[a[i]] > bHash[a[i]])
                {
                    aHash[a[i]] = aHash[a[i]] - bHash[a[i]];
                    bHash[a[i]] = 0;

                    if(aHash[a[i]] % 2 != 0)
                    {
                        flag = true;
                        break;
                    }
                }
                else
                {
                // if aHash[a[i]] < bHash[a[i]] , update bHash[a[i]] and make 
                // aHash[a[i]] = 0. If bHash[a[i]] % 2 != 0 means it can not be 
                // swapped. Such array is not possible.
                    if(aHash[a[i]] < bHash[a[i]])
                    {
                        bHash[a[i]] = bHash[a[i]] - aHash[a[i]];
                        aHash[a[i]] = 0;

                        if(bHash[a[i]] % 2 != 0)
                        {
                            flag = true;
                            break;
                        }
                    }
                }
                
                
            }   
        }

        // whether any bHash[b[i]] % 2 != 0, such condition must not be accepted
        for( int i = 0 ; i < size; i++)
        {
            if(bHash[b[i]] > 0 && bHash[b[i]] % 2 != 0)
            {
                flag = true;
                break;
            }
        }

        // Now we have elements in frequency array which are swapable. The compulsory 
        // elements has been removed. 
        // So now our logic will be for, how to swap elements 

        int aHashMultiple;
        int bHashMultiple;
        int totalMultiple;
        int i = 0;
        int j = size-1;
         
        if(!flag)
        {
            
            for( int i = 0, j = size-1; i < size && j >= 0 ;)
            {
                 if(aHash[a[i]] > 0)
                {
                    while(bHash[b[j]] == 0)
                    {
                        j--;
                    }
                    aHashMultiple = aHash[a[i]] / 2;
                    bHashMultiple = bHash[b[j]] / 2;
                    
                    
                    totalMultiple = min ( aHashMultiple, bHashMultiple);
                    
                    if(smallerElement == a[0])
                    {
                        if( i == 0)
                            total += min(a[0], b[j]);
                        else
                        {
                            total +=  min(a[0], b[j]);
                            total +=  min(a[0], a[i]);
                        }
                    }
                    else
                    {
                        if(i == 0)
                            total += min(b[0], a[j]);
                        else
                        {
                            total += min(b[0], a[j]);
                            total += min(b[0], b[i]);
                        }
                    }
                    
                    total *= totalMultiple;
                
                    aHash[a[i]] -= 2 * totalMultiple;
                    bHash[b[j]] -= 2 * totalMultiple;

                    if(aHash[a[i]] == 0)
                        i++;
                    if(bHash[b[j]] == 0)
                        j--;    
                }
                else
                {
                    i++;
                }
                   
            }
        }
        if(!flag)
            cout<< total <<endl;
        else
            cout<<"-1"<<endl;
     
    }
    return 0;
}

但上述代码未被接受。
有人可以改进此代码/逻辑吗?


共1个答案

匿名用户

假设您有两个数组:

A: 1 5 5
B: 1 4 4

我们知道我们想要向下移动一个5,向上移动一个4,因此我们必须选择:用4交换5(成本min(4,5)=4)或者使用最小元素来实现相同的结果,进行两次交换:

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    

所以我们每次交换的问题都是这样的。 是直接交换好,还是使用最小元素作为Pivot交换两次好?

简而言之,让M成为两个数组中的最小元素,并且您希望将I交换为J。 互换的成本为

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

所以只要找出你需要做的所有掉期,应用这个公式,把结果求和就可以得到你的答案。