Voici son énoncé car il faut faire les deux précédents pour pouvoir le débloquer:
Énoncé
Dans une liste de nombres entiers, une répétition est une paire de nombres égaux qui sont côte à côte. Par exemple, dans la liste 1 3 3 4 2 2 1 1 1, il y a quatre répétitions : les deux 3, puis les deux 2, puis les deux 1 qui suivent, et enfin les deux 1 de la fin de la liste.
On vous donne une liste de nombres entiers. Écrivez un programme qui calcule le nombre minimum de répétitions qu'il peut rester dans la liste une fois que l'on a retiré toutes les occurrences d'un des nombres.
Entrée
La première ligne de l'entrée contient un entier nbNombres, avec 2 ≤ nbNombres ≤ 50 000.
Les nbNombres lignes suivantes contiennent chacune un entier compris entre 0 et nbNombres.
Sortie
Vous devez afficher un nombre : le nombre minimum de répétitions qu'il est possible d'obtenir après avoir supprimé toutes les occurrences d'un des nombres de la liste.
Exemples
Voici un exemple d'entrée :
9
1
3
2
2
3
4
4
2
1
La liste de 9 nombres est "1 3 2 2 3 4 4 2 1". Elle contient deux répétitions (les deux premiers 2 et les deux 4) :
retirer les 1 laisse les deux répétitions ;
retirer les 2 rapproche les trois, donc on a supprimé une répétition et en rajoute une. Il reste donc deux répétitions ;
retirer les 3 laisse les deux répétitions ;
retirer les 4 ne laisse qu'une répétition.
Si on supprime toutes les occurrences du nombre 4, il reste une seule répétition. Il n'est pas possible d'en obtenir moins, donc votre programme doit afficher : 1
Mon code marche sur plusieurs test mais ne les réussi pas tous, je dois oublier de traiter un cas mais je ne vois pas lequel, voici mon code:
#include<bits/stdc++.h>
using namespace std;
int nombre[50001] = {0};
int rep[50001] = {0};
int main(){
int nb;
cin>>nb;
cin>>nombre[0];
int total = 0;
for (int i=1; i<nb;i++){
cin>>nombre[i];
if (nombre[i] == nombre[i-1]){
rep[nombre[i]] ++;
total++;
}
}
int a = 1;
int b = 1;
while(a<nb){
if (rep[nombre[a]]>0){
while(nombre[a] == nombre[b]){
b++;
}
if (nombre[a-1] == nombre[b]){
rep[nombre[a]] --;
b--;
}
}
b++;
a = b;
}
int maxi = 0;
for (int i =0; i<50001;i++){
if (rep[i]>=maxi){
maxi= rep[i];
}
}
cout<<total-maxi;
}
si vous pouviez éclairer ma lanterne, je serais vraiment très reconnaissant. (je connais aussi Python et C donc si vous avez des solutions dans ces langages, je suis aussi preneur)
