Salve a tutti, ho un problema da risolvere e non riesco a pensare a un algoritmo risolutivo, vi spiego il problema e vediamo se sapete indirizzarmi sulla giusta strada^^

C'e' una strada che parte dal km 0, e ogni tot kilometri c'e' un paese, per un totale di n paesi:

0______4______7__8______________15__.....

io devo piazzare k pizzerie in questi paesi, ad esempio una in quello a 4 chilometri, una a 15 ecc

Devo farlo in modo che la distanza che gli abitanti devono percorrere sia minima. Ad esempio con pizzeria in 4 e 15, la distanza e'
4+0+3+4+0, ossia la somma che gli abitanti di ogni paese fanno per andare alla pizzeria piu vicina.

Io non ho idea di come fare, le ho pensate tutte, algoritmi di cammini minimi, ordinamento e qualsiasi cosa ho pensato nn riesco a risolverlo...help please^^