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.
allora innanzi tutto grazie, scusami se non ti ho risposto ma effettivamente ha senso quello che dici (probabilmente qualche mese fa non avevo voglia di pensarci) e ritornandoci adesso sono riuscito a tirare giù un algoritmo che dovrebbe funzionare, peccato che non funziona…
int n, k; cin>>n>>k;
vector<int> v(n);
set<int> s;
pair<int, int> best = {0, 0}; //{balance, filiale}
for(int i = 0; i < n; ++i){
cin >> v[i];
}
int balance = v[n-1] - v[0];
s.insert({v[0], v[n-1]});
for(int i = 0; i < k - 2; ++i){
for(auto it1 = s.begin(), it2 = next(s.begin()); it2 != s.end(); ++it1, ++it2){
int mid = (*it1 + *it2) / 2;
int high = *lower_bound(all(v), mid), low = *prev(lower_bound(all(v), mid));
int lowbal = min(low - *it1, *it2 - low), highbal = min(high - *it1, *it2 - high);
if(lowbal > best.first){
best.first = lowbal;
best.second = low;
}
if(highbal > best.first){
best.first = highbal;
best.second = high;
}
}
s.insert(best.second);
balance = best.first;
best = {0, 0};
}
non è elegantissimo, però il concetto è: se ho 2 filiali, le ho già trovate perchè sono la prima e l’ultima. se ne ho 3 o più, prendo dal set tutte le coppie di filiali selezionate al momento, (inizialmente le prime 2), e per ogni coppia cerco nel vettore la filiale che ha la distanza minima, tra le due coppie di filiali già scelte, massima. quindi con l’input:
6 4
0 40 60 85 90 100
inizialmente nel set ho {0, 100}, quindi una sola coppia, allora controllo con lower bound le due filiali che si avvicinano di più alla filiale perfetta, ovvero 50 (0 + 100 / 2). otterrò le due filiali: high = 60 e low = 40. Di conseguenza controllo quella con il bilanciamento più alto. Entrambe sono uguali, di conseguenza prende la prima, ovvero 40, l’aggiungo nel set, quindi : {0, 40, 100} e rifaccio lo stesso procedimento… tra 0 e 40 troverà 40 e 0, quindi il bilanciamento sarà 0, e tra 40 e 100 troverà 85 e 60 ma sceglierà 60 perchè con il bilanciamento più alto. di conseguenza {0, 40, 60, 100} e il bilanciamento sarà 20… ao a me sembra corretto come ragionamento, e non capisco dove pecca, secondo me in qualche caso particolare dove scegliere tra due filiali uguali non è indifferente, però odio sto problema quindi se riuscite ad aiutarmi l’ultima volta ve ne sarei grato. grazie comunque per tutte le risposte precedenti 
Se provi con questo input:
6 4
0 40 60 85 90 130
ottieni 30 mentre il risultato corretto è 40.
ah, quindi il bilanciamento se aggiungo una filiale può non scendere, ma soprattutto c’è un errore nel calcolo della filiale migliore, eh ora che ci penso bene effettivamente devo cercare il valore diviso le filiali che devo prendere, non in base a quelle che ho selezionato al momento, provo a cambiare il codice e vedo se riesco a implementare, comunque ti devono fare santo, grazie
ho risolto usando come base le funzioni monotone, cercando il l’ultimo true che soddisfa la condizione (l’ultima distanza a cui posso posizionare una filiale probabilmente è quello che mi volevate far capire, ma non le avevo studiate quindi non riuscivo ad arrivarci, metto come soluzione quel messaggio solamente perche ci sono arrivato rileggendo quello, ringrazio ugualmente tutti per l’aiuto