Programme Leçon 57 sur 148 · La vitesse sans le cache
La vitesse sans le cache

Borner la recherche aux 200 adresses qui comptent

Pourquoi c'est important « Trouve le meilleur » sonne comme « regarde chacun ». Souvent, une simple borne te dit que rien plus bas dans la liste ne peut gagner, et tu peux t'arrêter.

Une commande peut partir de n'importe lequel de 50 000 entrepôts. La liste arrive triée par distance au client, le plus proche d'abord. L'expédition coûte 12p par km, et chaque entrepôt ajoute ses propres frais de manutention, qui ne dépassent jamais 5 000p. Chaque fiche d'entrepôt se trouve derrière un service de stock lent, donc chaque fiche lue coûte.

(distance_km, fee, name)   # cost = distance_km * 12 + fee
À ton tour

Écris cheapest(tape). tape est une Tape non vide de fiches (distance_km, fee, name) triées par distance_km croissante. Le coût vaut distance_km * 12 + fee, et chaque frais est entre 0 et 5 000. Renvoie le name de l'entrepôt le moins cher ; en cas d'égalité de coût, le plus proche ; si ça reste égal, celui qui vient en premier dans la liste. Budget : lis au plus 2 000 fiches sur 50 000. len(tape) est gratuit.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.