Non so cosa domandarmi e cosa fare, so che va fatta una ricerca, ma non so cosa cercare, potete aiutarmi a capire che domandarmi e come comportarmi quando mi trovo davanti a questi tipi di problemi?
grazie in anticipo.
Ciao, uno dei modi per approcciare questo tipo di problemi è cercare di capire come appare la disposizione ottimale che massimizza la distanza tra due filiali.
Una volta posizionate le filiali, la distanza raggiunta è il valore minimo, del valore assoluto, della differenza del posizionamento dei chilometraggi tra due filiali.
Si può notare come questo calcolo si possa ottimizzare pensando che per ogni filiale posizionata, ci interessa al più conoscere il valore della prima filiale a sinistra e la prima a destra (é ovvio siccome le distanze di altre filiali saranno sicuramente maggiori di queste due).
Posizionamo la prima filiale al primo chilometraggio possibile. Notare che la prima filiale posizionata non ha filiali a sinistra e ciò ci permette di pensare solo al posizionamento di quella alla sua destra.
Pensiamo a come posizionare la seconda filiale.
Siccome vogliamo essere molto cauti, proviamo a posizionarla ad almeno 1km di distanza dalla prima. Per cui posizioniamo al primo chilometraggio che ci renda possibile mantenere la distanza dalla prima di almeno 1km.
Pensiamo a come posizionare la terza filiale. Non ha senso posizionarla tra la prima e la seconda, altrimenti perdiamo la capacità di poter badare solo alla filiale alla nostra destra. Partendo dalla posizione della seconda filiale, troviamo il primo chilometraggio che soddisfi la precedente condizione.
In questo modo puoi posizionare le filiali in modo furbo. Ora per trovare la distanza massima non ti resta che cercare il valore massimo.
Se puoi posizionare le filiali ad una distanza di X chilometri, sicuramente puoi posizionare ad una distanza di X-1 chilometri.
Se non puoi posizionare le filiali ad una distanza di X chilometri, sicuramente non puoi posizionare ad una distanza di X+1 chilometri.
Scusami tanto, ma non penso di aver capito bene: Sicuramente noi posizioniamo la prima filiale al primo chilometraggio disponibile, e l’ultima all’ultimo. Ora assumiamo F=3, chiamiamo le filiali F_{k} indicizzate da 0 a k-1, e l’indice del primo chilometraggio v[d] >= (F_{k-1}+ F_2 )/ 2 . Ora possiamo piazzare F_1 al max(F_{k-1} - v[d], v[d-1] - F_0). Ora suppongo questo sia un modo giusto per approcciare il problema, solo che non riesco a capire come va ragionato quando entrano in gioco più filiali: è giusto se sostituisco F_0 con la filiale che ho appena scelto?
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
void fast() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
}
void print(vector<int> const &input){ //se non usi vector<int> cambialo
for (int i = 0; i < input.size(); i++) cout << input.at(i) << ' ';
}
ll solve(ll f, vector<ll> &v, ll n, ll d, ll sol, ll best, ll sx, ll dx){
if(d > dx) return best;
auto x = lower_bound(v.begin(), v.end(), d);
if(dx - *x > *(x-1) - sx){
sol = dx - *x;
sx = *x;
}else{
sol = *(x-1) - sx;
sx = *(x-1);
}
best = min(best, sol);
return solve(f-1, v, n, (dx + sx) / (f - 1), sol, best, sx, dx);
}
int main(){
fast();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ll n, f; cin >> n >> f;
vector<ll> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
cout<<solve(f-1, v, n, (v[n-1] + v[0]) / (f-1), (v[n-1] - v[0]), (v[n-1] - v[0]), v[0], v[n-1]);
return 0;
}
ho fatto questo codice che fa 20/100 secondo quello che ho appena detto (scusa se è scritto malissimo ma stavo seguendo il flusso di coscienza). Se riesci puoi farmi capire meglio dove sbaglio a ragionare? Grazie comunque per la risposta.
Con questo input:
5 4
1 4 6 8 9
il codice restituisce 3 mentre la risposta corretta è 2.
In pratica il bilanciamento non è la max distanza tra 2 filiali consecutive ma dev’eesere, tra le F filiali da scegliere, quello con il max valore della minima distanza tra 2 di esse.
Quindi la scelta migliore è {1, 4, 6, 9} dove il bilanciamento max è dmin = 2 e non ad esempio {1, 4, 8, 9} dove dmin = 1.
Si ho capito cosa intendi, e il mio codice già doveva fare questo, ho messo un if che controlla se l’iteratore precedente è una filiale già presa, se si, prende a prescindere la filiale. Ora con il tuo esempio l’output è corretto, ma il mio dubbio rimane lo stesso, in questo modo, se entrano in gioco più filiali e magari prendo sempre la fiiliale più comoda, come faccio a sapere quante possibili filiali posso saltare: se ne salto troppe, magari arrivo alla fine senza una soluzione ottima o addirittura senza poter costruire tante filiali quante me ne servono. Sinceramente questa categoria di problemi la odio, in questi casi comprendo veramente tanto quanto siano importanti i professori, sono disperso in un insieme infinito di argomenti in cui perdo settimane se non mesi, per poterli assimilare discretamente. Sono consapevole anche del fatto che se dico di non capire ogni volta posso risultare pesante, non so più se a questo punto conviene chiedervi la soluzione e spiegazione del problema, perchè sto pensando di lasciarlo perdere e andare avanti. Comunque ringrazio tutti per le risposte e l’aiuto che mi avete provato a dare.
Puoi fare, ad esempio, una ricerca binaria da 0 a K[N-1] e controllare per ogni distanza se riesci a coprire tutte le filiali con quel valore.
Quando trovi questo valore ottieni la max distanza minima tra tutte le possibili filiali.