E’ da 2 giorni che cerco di risolvere questo problema…non riesco a trovare un algoritmo risolutivo.
Per quanto ho estrapolato una soluzione ottimale presenta sempre come filiali la prima e l’ultima, e, una soluzione “perfetta” , ha filiali equidistanti di (K[N-1]-K[0])/(F-1) unità.
Per esempio se dovessi scegliere 4 filiali tra una fila che presenta come prima filiale 0, e come ultima 1000, la soluzione perfetta sarebbe 0,333,666,1000. Ho pensato quindi di scegliere i numeri che si avvicinassero il più possibile alla soluzione “perfetta” ma in casi tipo:
F = 4
0 200 250 333 400 1000
sceglierei 0 333 400 1000
quando la soluzione è in realtà 0 200 400 1000
Ho pensato ad un approccio ricorsivo ma considerando N, credo andrei fuori tempo.
Qualche suggerimento a come approcciare il problema?
Quella che tu trovi come distanza nella “soluzione perfetta”, la puoi utilizzare intanto come limite di partenza: sicuramente meglio di così non puoi fare, quindi partendo dall’inizio puoi provare a vedere se scegliendo le filiali ad almeno quella distanza riesci a piazzarne il numero richiesto. Se non puoi piazzarne quante serve, allora dovrei diminuire questo numero, che è anche la soluzione richiesta dal problema.
A questo punto, ti basta continuare a diminuire di uno ogni volta fino a ché non trovi un valore valido, che ti permette di “distribuire” K filiali ad ALMENO quella distanza tra loro.
A questo punto però, ti accorgerai che l’algoritmo ha una complessità troppo grande per rientrare nei limiti di tempo: anziché provare tutti i valori, devi pensare a una ricerca più rapida di questo valore 
Ti voglio bene 
L’ho risolto, grazie.
Riapro la discussione dopo molto tempo:
Ho appena provato a svolgere il problema e la soluzione che avevo pensato(aiutato anche dal tag binary_search) è proprio quella descritta ma ho commesso un errore nel codice che non riesco a trovare(Execution killed with signal 11 (could be triggered by violating memory limits))
Questo è il codice commentato, anche se l’errore non dovrebbe essere di logica riassumo il mio algoritmo:
-
Calcolo la distanza ottimale con la formula
*A.rbegin()-*A.begin())/(f-1), si verifica quando esistono f città equidistanti tra loro comprese la prima e l’ultima. -
Tramite la ricerca binaria cerco il valore v con 1<=v<=distanza ottimale maggiore che soddisfi la richiesta.
Utilizzo un multiset(per l’upper_bound() e la lower_bound()) per tutte le citta, ed una deque per ognuno dei \log_2 distanzaottimale che contiene le città scelte per la combinazione.
Dove è l’errore?