Je crois que j'ai une solution (peut-être pas optimale, j'en sais rien).
1) On fait une première passe pour déterminer qui de a ou de b est le plus fort (celui qui a gagné le plus d'épruves parmi les N épreuves). F est le fort, f le faible.
2) On sélectionne pour f toutes les épreuves gagnées par f. On en a donc déja X <= N/2
3) On sélectionne ensuite pour f, parmi les épreuves restantes, les N/2 - X meilleurs scores de f, sans regarder le score de F. On a alors la totalité des N/2 épreuves de f.
4) Il ne reste donc plus qu'à assigner les N/2 épreuves restantes à F.
Par contre, je ne sais pas si ça gère bien d'éventuelles égalités.
[^] # Re: une autre idée
Posté par arnaudus . En réponse au message Algorithme optimum. Évalué à 2.
1) On fait une première passe pour déterminer qui de a ou de b est le plus fort (celui qui a gagné le plus d'épruves parmi les N épreuves). F est le fort, f le faible.
2) On sélectionne pour f toutes les épreuves gagnées par f. On en a donc déja X <= N/2
3) On sélectionne ensuite pour f, parmi les épreuves restantes, les N/2 - X meilleurs scores de f, sans regarder le score de F. On a alors la totalité des N/2 épreuves de f.
4) Il ne reste donc plus qu'à assigner les N/2 épreuves restantes à F.
Par contre, je ne sais pas si ça gère bien d'éventuelles égalités.