Il existe 2 tableaux i / p. Ils sont identiques lorsqu'ils contiennent exactement les mêmes numéros. Pour les rendre identiques, nous pouvons échanger leurs éléments. L'échange aura un coût. Si nous échangeons les éléments a et b, alors cost = min (a, b).
Tout en rendant le tableau identique, le coût devrait être minimum.
S'il n'est pas possible de rendre le tableau identique, alors imprimez -1.
#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; }
Ici, j'ai permuté (2,7) et (2,6). Donc, Coût minimum = 2 + 2 = 4.
Logique:
Créez 2 cartes qui enregistreront la fréquence des éléments du tableau i / p.
si l'élément "a" dans aMap est également présent dans bMap, alors nous devons considérer le nombre de permutation pour a = abs (freq (a) dans aMap - freq (a) dans bMap)
si la fréquence des éléments est "impaire", alors impossible de les rendre identiques.
sinon, ajoutez le total des échanges à partir des deux cartes et recherchez le coût à l'aide de
coût = plus petit élément * total des swaps
Voici le code
i/p: 3 6 6 2 2 7 7 3 o/p : 4
Aucune erreur dans le code ci-dessus mais une mauvaise réponse et ne pas être accepté.
Quelqu'un peut-il améliorer ce code / cette logique?
4 Réponses :
Supposons que vous ayez 2 tableaux:
min( min(i,j), 2 * m )
Nous savons que nous voulons déplacer un 5 vers le bas et un 4 vers le haut, nous devons donc choisir les options: permuter 4 par 5 (avec un coût min (4, 5) = 4
) ou en utilisant l'élément minimum pour obtenir le même résultat, en faisant 2 swaps:
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
Donc la question que nous faisons à chaque échange est-ce. Vaut-il mieux échanger directement ou échanger deux fois en utilisant l'élément minimum comme pivot?
En un mot, laissez m
être l'élément minimum dans les deux tableaux et vous voulez échanger i
pour j
. Le coût du swap sera de
A: 1 5 5 B: 1 4 4
Alors découvrez tous les swaps que vous devez faire, appliquez cette formule et additionnez les résultats pour obtenir votre réponse.
J'ai mis à jour le code et suivi ce que vous avez dit. Mais toujours en me donnant une mauvaise réponse et en ne me faisant pas accepter. Est-ce que je manque un étui de coin? (le code n'a pas d'erreur et donne la bonne réponse pour mes entrées.)
Êtes-vous sûr d'échanger le nombre minimum d'éléments possible? Êtes-vous sûr de gérer correctement les cas où il est impossible de résoudre (c'est-à-dire lorsqu'un nombre apparaît un nombre impair de fois)?
Pour réduire le coût d'échange, consultez la réponse de Daniel. Pour savoir si le swap est réellement possible, veuillez faire ce qui suit, les swaps ne sont en fait possibles que si vous avez un nombre pair d'éléments au total, de sorte que vous puissiez les répartir uniformément, donc si vous avez 2, 4 ou 6 5 vous êtes bon, mais si vous avez 1, 3 ou 5, retournez -1. C'est impossible si votre nombre de doublons d'un nombre est impair. Pour résoudre réellement le problème, il existe une solution très simple à laquelle je peux penser, car elle coûte un peu cher, il vous suffit de vous assurer qu'il y a le même nombre d'éléments de chaque côté, donc la façon simple de le faire serait be pour déclarer un nouveau tableau:
1 1 0 0 1 1 //one two one three zero four zero five 1 six and 1 seven
Prenez la moitié de chaque élément, donc quelque chose comme:
i/p: 3 6 6 2 2 7 7 3 o/p : 4
Prenez la moitié de chaque élément de temp . Lorsque vous voyez un élément qui correspond à un élément de votre tableau de comptage, chaque fois que vous voyez un 1, décrémentez l'index du tableau de comptage de 1, donc quelque chose comme count [1] -; En supposant que le compte commence à 0. Si l'index est à zéro et que l'élément est celui-là, cela signifie qu'un échange doit être effectué, dans ce cas, trouvez le min suivant dans l'autre tableau et échangez-le. Bien qu'un peu cher, mais c'est le moyen le plus simple auquel je puisse penser. Par exemple, dans votre cas:
int count[max element in array - min element in array]; for(int i = 0; i < temp.size(); i++){ count[temp[i]]++; }
Nous aurions besoin de stocker l'index min comme 2. Parce que c'est le plus petit. Nous aurions donc un tableau qui ressemble à ce qui suit:
int temp[size of original arrays]; //Go through both arrays and store them in temp
Vous passeriez par le premier tableau, quand vous voyez le second six, votre index de tableau à 6 serait zéro , vous savez donc que vous devez l'échanger, vous trouverez le min dans l'autre tableau, qui est 2, puis échangez 6 avec 2, après les wards, vous pouvez parcourir le tableau en douceur. Enfin, vous passez par le deuxième tableau, ensuite, lorsque vous voyez les 7 derniers, il cherchera le min de l'autre côté, les échangez ...., ce qui fait deux, notez que si vous aviez 3 deux sur un côté et un deux sur l'autre, il y a de fortes chances que les trois deux vont de l'autre côté, et 2 d'entre eux reviendront, car nous échangeons toujours le min, donc il y aura toujours un nombre pair de façons de réorganiser les éléments. p >
@ user1745866 Vous pouvez simplifier votre tâche de détermination de la réponse -1 en utilisant uniquement la variable:
nous avons int x = 0 et nous ferons simplement XOR de tous les entiers i / p comme celui-ci:
int x = 0; for(int i=0;i<n;i++){ cin>>a[i]; x = x^a[i]; } for(int i=0;i<n;i++){ cin>>b[i]; x = x^b[i]; } if(x!=0) cout<<-1; else{ ...do code for remain 2 condition... }
Maintenant, le point est de savoir comment cela fonctionnera car, comme tous les nombres des deux tableaux devrait se produire seulement un nombre pair de fois et lorsque nous faisons une opération XOR d'un nombre quelconque qui s'est produit un nombre pair de fois, nous obtiendrons 0 .... sinon, ils ne peuvent pas être des tableaux identiques.
Maintenant, pour la deuxième condition (qui donne la réponse 0), vous devez utiliser multimap afin de pouvoir comparer directement les deux tableaux en complexité temporelle O (n) comme si tous les éléments des deux tableaux sont identiques, vous pouvez afficher: 0
( Remarque: je suggère multimap parce que 1: Vous auriez les deux tableaux triés et tous les éléments seraient là, cela signifie également des doublons.
2: parce qu'ils sont triés, s'ils sont constitués du même élément à la même position, nous pouvons afficher: 0 sinon vous devez continuer pour votre 3ème condition ou échanger les éléments.)
Bien que ce code puisse résoudre la question, y compris une explication expliquant comment et pourquoi cela résout le problème aiderait vraiment à améliorer la qualité de votre post, et entraînera probablement plus de votes à la hausse. N'oubliez pas que vous répondez à la question des lecteurs à l'avenir, pas seulement à la personne qui la pose maintenant. Veuillez modifier votre réponse pour ajouter des explications et donner une indication des limitations et hypothèses applicables.
n'utilisez pas de tableaux de longueur variable,
a [size]
etn [size]
etaHash [N]
etbHash [N]
, même si le compilateur les accepte (comme g ++) la taille utilisée au moins à cause de la valeur N est probablement hors de la taille de la pileCurieusement, hier, nous avons eu Rendre deux tableaux identiques en échangeant des éléments [fermé] a> :)
la bonne solution est de swap
(6, 7)
donc le coût est de1
. Je n'ai aucune idée de pourquoi votre code est si complexe. Je pense que c'est faisable en 20 lignes.Dans
aHash [a [i]]
comment pouvez-vous supposer quea [i]
est un index valide dans aHash aprèscin >> a [i];
? idem dansbHash [b [i]]
@MarekR Si nous échangeons (6,7), le coût sera de 6. (coût = min (élément d'échange a, b))
@bruno J'ai pris un tableau assez grand. c'est-à-dire 2 * 10 ^ 6. La plage est donnée dans la question. Array n'ira pas au-delà de cette plage.
cela n'a aucun sens de les avoir dans la pile, si j'entre 987654321 pour
cin >> a [i];
etc vous sortez de vos tableaux en faisantaHash [a [i ]]
@ user1745866 Mais le code ci-dessus n'est pas accepté. Quel est le problème pouvez-vous me dire quelles erreurs sont survenues ou quelle est la sortie attendue ?? Quel est le problème??