有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;
}
但上述代码未被接受。
有人可以改进此代码/逻辑吗?
假设您有两个数组:
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 )
所以只要找出你需要做的所有掉期,应用这个公式,把结果求和就可以得到你的答案。