je te donne un array et un entier n ton but est de me renvoyé la plus petite somme de n…
- User
je te donne un array et un entier n ton but est de me renvoyé la plus petite somme de n différence dans le tableau en python et tu ne peux utilisé que une seul fois chaque terme je veux aussi une complexité mémoire de maximum O(N)
exemple : """ Exemple d'entrée 7 2 1 4 5 5 6 9 12
Exemple de sortie: 2 """
""" Exemple d'entrée 5 2 10 6 4 1 3 Exemple de sortie 4 """
Reason like this :
possible error and limits case
Solution for this
and how to solve this quiclky without lots of memory
- Assistant
Pour résoudre ce problème, nous devons trouver la somme minimale des n plus petites différences dans un tableau donné, en utilisant chaque élément au plus une seule fois. Pour garantir une complexité mémoire de (O(N)), nous devons optimiser notre approche en utilisant un algorithme efficace.
Analyse du Problème
Exemple 1:
Entrée: 7 2 1 4 5 5 6 9 12 Sortie: 2Exemple 2:
Entrée: 5 2 10 6 4 1 3 Sortie: 4Interprétation:
- Nous devons sélectionner n paires d'éléments dans le tableau tel que la somme des différences absolues de ces paires soit minimale.
- Chaque élément du tableau ne peut être utilisé qu'une seule fois dans au plus une paire.
Approche Solution
-
Tri du Tableau:
- Commencez par trier le tableau. Cela facilite la recherche des plus petites différences car les éléments similaires sont adjacents.
-
Utilisation d'une Approche Dynamique (Programmation Dynamique):
- Définissez un tableau
dpoùdp[i]représente la somme minimale des différences pour les premièresiéléments avec un certain nombre de paires. - À chaque étape, vous avez le choix soit de former une paire avec l'élément actuel et le précédent, soit de ne pas former de paire avec l'élément actuel.
- Définissez un tableau
-
Optimisation de la Mémoire:
- Puisque nous ne stockons que les résultats pertinents à chaque étape, nous pouvons optimiser la mémoire en utilisant des variables pour stocker les états précédents au lieu d'un tableau complet.
Gestion des Cas Limites et Erreurs
-
Tableau avec un nombre insuffisant d'éléments:
- Si le nombre d'éléments dans le tableau est inférieur à
2n, il n'est pas possible de formernpaires distinctes.
- Si le nombre d'éléments dans le tableau est inférieur à
-
Éléments identiques:
- Gérer correctement les éléments identiques, car leur différence est zéro, ce qui est souhaitable pour minimiser la somme.
-
Valeurs Négatives:
- Si le tableau contient des nombres négatifs, les différences absolues doivent toujours être positives.
Solution Optimisée en Python
Voici une implémentation en Python qui suit l'approche décrite ci-dessus:
def min_sum_of_differences(N, n, array): if 2 * n > N: return -1 # Impossible de former n paires distinctes array.sort() INF = float('inf') # dp[k] représentera la somme minimale pour k paires jusqu'à l'élément courant dp_prev = [INF] * (n + 1) dp_prev[0] = 0 # Base case: 0 paires ont une somme de 0 for i in range(1, N): dp_curr = dp_prev.copy() for k in range(1, n + 1): if i >= 1: # Essayer de former une paire avec i et i-1 if dp_prev[k - 1] + (array[i] - array[i - 1]) < dp_curr[k]: dp_curr[k] = dp_prev[k - 1] + (array[i] - array[i - 1]) dp_prev = dp_curr # Mettre à jour pour la prochaine itération return dp_prev[n] if dp_prev[n] != INF else -1 # Lecture des entrées if __name__ == "__main__": import sys input_data = sys.stdin.read().split() idx = 0 T = 1 # Nombre de tests, à ajuster si nécessaire for _ in range(T): N = int(input_data[idx]); idx += 1 n = int(input_data[idx]); idx += 1 array = list(map(int, input_data[idx:idx + N])); idx += N result = min_sum_of_differences(N, n, array) print(result)Explications du Code
-
Tri du Tableau:
array.sort() -
Initialisation du Tableau
dp_prev:dp_prev[k]représente la somme minimale des différences pourkpaires jusqu'à l'élément précédent.- Initialement, la somme pour 0 paire est 0, et infinie pour les autres.
-
Itération et Mise à Jour de
dp_prev:- Pour chaque élément, nous essayons de former une paire avec l'élément précédent et mettons à jour la somme minimale des différences pour chaque nombre possible de paires.
-
Résultat:
- Après avoir parcouru tout le tableau,
dp_prev[n]contiendra la somme minimale desndifférences si possible, sinon-1.
- Après avoir parcouru tout le tableau,
Tests et Validation
Test 1:
Entrée: 7 2 1 4 5 5 6 9 12 Sortie: 2Explication:
- Paires possibles avec sommation minimale: (4,5) et (5,6) → 1 + 1 = 2
Test 2:
Entrée: 5 2 10 6 4 1 3 Sortie: 4Explication:
- Paires possibles avec sommation minimale: (1,3) et (4,6) → 2 + 2 = 4
Conclusion
Cette approche garantit une complexité mémoire de (O(N)) en utilisant uniquement des variables pour stocker les états précédents. De plus, elle est efficace en temps étant donné que nous avons trié le tableau initialement. Assurez-vous de gérer les cas limites où il n'est pas possible de former le nombre requis de paires.