There are 2 i/p array's. They are identical when they have exactly same numbers in it. To make them identical, we can swap their elements. Swapping will have cost. If we are swapping a and b elements then cost = min(a, b).
While making array's identical, cost should be minimum.
If it is not possible to make array identical then print -1.
i/p:
3 6 6 2
2 7 7 3
o/p :
4
Here I have swapped (2,7) and (2,6). So min Cost = 2 + 2 = 4.
Logic :
Make 2 frequency array of i/p array's.
if frequency of elements % 2 != 0 , then not possible to make them identical.
else , Swap smallest elements from both the arrays, with other elements.
Here is the code
#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;
}
But the above code is not getting accepted.
Can anyone improve this code / logic ?
Aucun commentaire:
Enregistrer un commentaire