Ton raisonnement "au pire des cas" est valable dans le cas où la répartition des nombres est 'idéale', c'est à dire que les 2 max de deux personnes ne soient pas dans la même urne.
Il est valable quelque soit la répartition.
Je montre (par l'absurde) qu'il y a un majorant au maximum.
Je ne montre pas (à toi de l'exhiber pour t'en convaincre) qu'il y a un minorant au maximum, le choix des deux plus grands maximum par personnes. Petit indice : il "suffit" de trier les 2 premières boules par personne, de les ranger bien adéquoitement dans les urnes et de remplir le reste correctement.
Le minorant = le majorant, CQFD.
Ça se généralise au cas k boules tirées. Le maximum sera toujours la somme des k n meilleures boules par personnes, il suffit de bien les arranger pour le tirage.
La complexité de ton problème chute drastiquement avec ce peu de maths et revient à un tri.
[^] # Re: Pire des cas
Posté par _kaos_ . En réponse au message Recherche algorithme de somme de denombrement. Évalué à 2. Dernière modification le 13 juin 2017 à 09:11.
Salut,
Il est valable quelque soit la répartition.
Je montre (par l'absurde) qu'il y a un majorant au maximum.
Je ne montre pas (à toi de l'exhiber pour t'en convaincre) qu'il y a un minorant au maximum, le choix des deux plus grands maximum par personnes. Petit indice : il "suffit" de trier les 2 premières boules par personne, de les ranger bien adéquoitement dans les urnes et de remplir le reste correctement.
Le minorant = le majorant, CQFD.
Ça se généralise au cas k boules tirées. Le maximum sera toujours la somme des k n meilleures boules par personnes, il suffit de bien les arranger pour le tirage.
La complexité de ton problème chute drastiquement avec ce peu de maths et revient à un tri.
Matricule 23415