Algorithme gourmand pour une distribution d'objets uniformes

Question

J'ai ce problème où j'ai besoin de concevoir un algorithme gourmand. Le problème est le suivant:

Une chocolaterie possède $ n $ magasins, qui sont reliés par une seule route. Chaque magasin a un approvisionnement limité $ c_i $ de chocolats. De plus, l'usine aimerait avoir la même quantité de chocolat dans chaque magasin. Par conséquent, ils ont embauché un chauffeur de camion pour transporter des chocolats entre les magasins, mais le conducteur mange deux barres de chocolat pour chaque kilomètre qu'il conduit.

Calculez la plus grande quantité de chocolat $ C $ Ils peuvent avoir dans chaque magasin.

Saisir: La position $ p_i $ et l'approvisionnement en chocolat $ c_i $ de chaque magasin. Les positions sont en augmentation de l'ordre trié.

Production: Le plus grand montant $ C $, tel que chaque magasin peut avoir un approvisionnement en chocolat au moins $ C $ Après que le chauffeur de camion a transporté les magasins.

J'ai un problème avec l'identification de la propriété Greedy Choice pour le problème. Jusqu'à présent, j'ai trouvé ce qui suit:

Le choix gourmand peut être la moyenne arithmétique minimale de deux magasins voisins moins le coût de livraison divisé par $ C $, mais il doit être plus grand ou égal à 1. J'ai trouvé l'équation suivante:$ee

Où le coût de livraison est $ 2 cdot | p_i - p_ {i-1} | $.

Je ne sais pas si cette approche est la bonne. Je suis ouvert aux indices et aux solutions partielles.