# Filiali Bilanciate

**URL:** <https://forum.olinfo.it/t/filiali-bilanciate/623>\
**Category:** Aiuto\
**Created:** [14 Giugno 2016, 5:28pm UTC](https://forum.olinfo.it/t/filiali-bilanciate/623 "2016-06-14T17:28:20Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![LucaSolbiati](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucasolbiati/32/223_2.png) [@LucaSolbiati](https://forum.olinfo.it/u/LucaSolbiati)\
**Post date:** [14 Giugno 2016, 5:28pm UTC](https://forum.olinfo.it/t/filiali-bilanciate/623/1 "2016-06-14T17:28:20Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [14 Giugno 2016, 6:22pm UTC](https://forum.olinfo.it/t/filiali-bilanciate/623/2 "2016-06-14T18:22:49Z")

</div>

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 🙂

---

<div class="post-metadata">

**Author:** ![LucaSolbiati](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucasolbiati/32/223_2.png) [@LucaSolbiati](https://forum.olinfo.it/u/LucaSolbiati)\
**Post date:** [14 Giugno 2016, 7:55pm UTC](https://forum.olinfo.it/t/filiali-bilanciate/623/3 "2016-06-14T19:55:00Z")

</div>

Ti voglio bene 😍  
L’ho risolto, grazie.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [20 Luglio 2017, 8:17pm UTC](https://forum.olinfo.it/t/filiali-bilanciate/623/4 "2017-07-20T20:17:11Z")

</div>

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](https://pastebin.com/0MHFjPQn) è il codice commentato, anche se l’errore non dovrebbe essere di logica riassumo il mio algoritmo:

1. 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.

2. 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?