Suppose given two arrays A and B, each of size n. If after sorting both arrays in non-descending order, they can be called identical if the ith element of both arrays are equal for each i(1<=i<=n). We can perform below operation zero or more times: choose two integers i and j (1≤i,j≤N) and swap A(i) with B(j). The cost of each such operation is min(A(i), B(j)). We have to find the minimum total cost to make the two sequences identical.
For example, A=1 B=2 .we can not make it identical so the answer is -1; A=1,2 B=2,1 This sequence is identical initially(when we sort), so the answer is 0. A=1,1 B=2,2 We can swap A1 with B2, which makes the two sequences identical, so the answer is 1(i.e, minimum of 1,2).
My Attempt to Question:
I stored the frequencies of all the elements of both the arrays(i.e, the union of both the array) and then checked if there is any element whose frequency in the union of both the arrays is odd then answer is -1 else I am storing elements from both arrays that are present in excess and swapping with element of higher value of another array element and computing my answer.
Here's my code :
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define BOOST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define ld double
#define pie 3.1415926536
#define inf INT_MAX
using namespace std;
bool check(map<ll,ll> mp)
{
for(auto i: mp) if(i.second%2) return true;
return false;
}
void solve()
{
ll n,ans=0,x; cin>>n;
map<ll,ll> mp,a,b;
vector<ll> vec1,vec2;
rep(i,0,n)
{
cin>>x;
mp[x]++;
a[x]++;
}
rep(i,0,n)
{
cin>>x;
mp[x]++;
b[x]++;
}
if(check(mp)) { cout<<"-1\n"; return; } //base condition
for(auto i: a)
{
auto j=b.find(i.first);
if(j==b.end())
{
x=(i.second)/2;
while(x--) vec1.pb(i.first);
}
else if(j->second!=i.second)
{
x=(abs(j->second-i.second))/2;
if(j->second>i.second) while(x--) vec2.pb(i.first);
else while(x--) vec1.pb(i.first);
}
}
for(auto i: b)
{
auto j=a.find(i.first);
if(j==a.end())
{
x=(i.second)/2;
while(x--) vec2.pb(i.first);
}
}
if(vec1.size()!=vec2.size()) { cout<<"-1\n"; return; }
sort(all(vec1));
sort(all(vec2),greater<ll>());
for(ll i=0; i<vec1.size(); ++i) ans+=min(vec1[i],vec2[i]);
cout<<ans<<"\n";
}
int main()
{
BOOST
int T; cin>>T;
while(T--) solve();
return 0;
}
Please help what's the error in my code. I am getting the wrong answer. Please check it and suggest any test case where my code will fail and which part is wrong in my code.
Aucun commentaire:
Enregistrer un commentaire