1
votes

Pour rendre le tableau identique en échangeant des éléments

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:

  1. Créez 2 cartes qui enregistreront la fréquence des éléments du tableau i / p.

  2. 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)

  3. si la fréquence des éléments est "impaire", alors impossible de les rendre identiques.

  4. 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 :


3
votes

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.


2 commentaires

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)?



1
votes

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 >


0 commentaires

1
votes

@ 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.)


0 commentaires

0
votes

Lien de problème https://www.codechef.com/JULY20B/problems/CHFNSWPS a>

ici pour calculer le nombre minimum de swap.nous aurons 2 cas

disons un exemple

    //code 
    l1.sort()
    l2.sort(reverse=True)
    sums=0
    for i in range(len(l1)):
            sums+=min(min(l1[i],l2[i]),2*minimum))
    print(sums)
    #print -1 if u get odd count of a key in total (means sums of count of key in both list)

cas 1. swap each pair wrt to min (l1, l2) = 1

step 1 swap single 2 of a pair of 2 from l1-> [1,1,2] [2,5,5] le coût est de 1
étape 2 permutation d'un seul 5 d'une paire de 5 de l1-> [1,5,2] [2,1,5] le coût est de 1
le coût total est de 2

cas 2. swap min de l1 avec max de l2 (répéter jusqu'à la fin des deux listes)

essayez de penser si nous trions en premier lister par ordre croissant et par ordre décroissant, alors nous pouvons minimiser les coûts.

l1=[2,2,5,5]
l2=[3,3,4,4]

L'astuce est que nous n'avons besoin de stocker que min (l1, l2) dans la variable, disons mn. Supprimez ensuite tous les éléments communs des deux listes.

l1=[5,2]
l2=[2,5]  cost is 2
total cost is 2

puis échangez chaque élément de l'index 0 à len (l1) -1 avec un saut de 2 comme 0,2,4,6 ..... parce que chaque voisin impair sera le même que le numéro précédent. après avoir effectué l'échange, le coût sera de 2 et

now list became l1=[2,2]
                l2=[5,5]

Disons un autre exemple

 l1=[1,2,2]
 l2=[5,5,1]

après avoir résolu wrt en min (l1 , l2) le coût total sera de 2 + 2 + 2 = 6
mais le coût après le tri de la liste sera permuté de ((2,4) et (5,3)) est 2 + 3 = 5
donc le swap minimum pour rendre la liste identique est min (5,6) = 5

l1=[1,2,2]
l2=[1,5,5]


1 commentaires

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.