Programme C++ : comptez le nombre d'opérations nécessaires pour que tous les cadeaux soient égaux en quantité

Supposons que nous ayons deux tableaux A et B, chacun de taille n. Il y a n cadeaux et nous voulons les offrir à des enfants. Le ième cadeau se compose de A[i] bonbons et de B[i] oranges. Lors d'un déménagement, nous pouvons sélectionner des cadeaux et effectuer l'une des actions suivantes -

• retirer un bonbon de ce cadeau (le cas échéant) p>

• retirer une orange de ce cadeau (le cas échéant) ;

• Retirez un bonbon et un cadeau orange de ce cadeau (le cas échéant).

Tous les cadeaux doivent être créés égaux. Cela signifie qu'après une série de mouvements, les deux Les conditions doivent être remplies : A[0] = A[1] = ... = A[n-1] et B[0] = B[1] = ... = B[n-1]. nous devons Trouvez le nombre minimum d'étapes requises pour que tous les cadeaux offerts soient égaux.

Catégorie de problèmes

Les problèmes ci-dessus peuvent être résolus en appliquant des techniques gourmandes de résolution de problèmes. La technologie des algorithmes gourmands est le type d’algorithme qui fournit actuellement la meilleure solution Choisissez plutôt que d’essayer toutes les solutions possibles. La technologie des algorithmes gourmands également Utilisé pour résoudre des problèmes d'optimisation, tout comme son grand frère la programmation dynamique. Actif Lors de la programmation, vous devez parcourir tous les sous-problèmes possibles et trouver celui qui est optimal solution, mais elle présente un inconvénient : elle nécessite plus de temps et d’espace. Par conséquent, dans divers La technique gourmande en scénarios est utilisée pour trouver la meilleure solution au problème. Même si c'est vrai ne donne pas la meilleure solution dans toutes les situations, s'il est conçu avec soin, il peut produire une solution plus rapidement que Problème de programmation dynamique. Les techniques gourmandes fournissent des solutions optimales locales problème d'optimisation. Des exemples de cette technique incluent le minimum de Kruskal et Prim Algorithme Spanning Tree (MST), codage de l'arbre de Huffman, chemin le plus court à source unique de Dijkstra Questions etc

https://www.tutorialspoint.com/data_structurals_algorithms/greedy_algorithms.htm

https://www.tutorialspoint.com/data_structurals_algorithms/dynamic_programming.htm p>

Donc, si l'entrée de notre problème est comme ceci A = [3, 5, 6] ; B = [3, 2, 3], alors la sortie est 6, Puisqu'il a été initialement pris dans B, maintenant B[0] devient [2, 2, 3], puis pris dans A[1], donc A = [3, 4, 6], puis encore de A[1], donc A = [3, 3, 6], puis de A[2] et B[2], donc ils à [3, 3, 5] et [2, 2, 2], puis de A[2] à A = [3, 3, 4], encore de A[2] à Que ce soit [3, 3, 3]. Alors maintenant, A a le même nombre de bonbons et B a le même nombre d’oranges.

Étapes

Pour résoudre ce problème, nous suivrons les étapes suivantes -

minA := inf
minB := inf
kq := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   minA := minimum of minA and A[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   minB := minimum of minB and B[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   kq := kq + maximum of (A[i] - minA) and (B[i] - minB)
return kq

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B){
   int minA = 999, minB = 999, kq = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      minA = min(minA, A[i]);
   for (int i = 0; i < n; i++)
      minB = min(minB, B[i]);
   for (int i = 0; i < n; i++)
      kq += max(A[i] - minA, B[i] - minB);
   return kq;
}
int main(){
   vector<int> A = { 3, 5, 6 };
   vector<int> B = { 3, 2, 3 };
   cout << solve(A, B) << endl;
}

Input

{ 3, 5, 6 }, { 3, 2, 3 }

Output

6

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!