Ciao, sto provando a risolvere sushi ed ero abbastanza sicuro di aver trovato una soluzione ma eseguo correttamente solo gli esempi. Non riesco a trovare bug né degli input che mi diano risultato sbagliato.
La mia idea è quella di:
- Ordinare i piatti per il tempo in cui finisco di mangiarli.
- Per ogni piatto, considero la soluzione fino al tempo in cui arriva il piatto e ci aggiungo il riempimento del mio piatto.
- Se questa soluzione è migliore della soluzione fino a questo piatto, la inserisco in un array insieme al tempo in cui finisco di mangiare questo piatto e poi passo avanti.
- Essendo i piatti ordinati per l’istante in cui finisco di mangiarli, posso assumere che anche il mio array sarà ordinato nella stessa maniera e quindi posso eseguire una binarysearch per trovare la soluzione fino al tempo che voglio (quando arriva un piatto).
- Inoltre so che la mia soluzione finale si troverà alla fine di questo array.
Questo dovrebbe dare la soluzione corretta secondo me perché prima che arrivi un piatto saranno già stati processati tutti quelli che potrebbero essere stati mangiati prima e poi viene presa la migliore soluzione fino a quel piatto, creando una nuova soluzione solo se supera quella attuale (con attuale intendo la soluzione per i piatti precedenti, non la soluzione fino al tempo di arrivo del piatto corrente)
In ogni caso qui il codice, l’errore è output non corretto
#include<bits/stdc++.h>
using namespace std;
struct piatto{
int somma; //quando finisco di mangiare il piatto
int inizio; //quando inizio a mangiare il piatto
int peso; //valore del piatto
bool operator<(piatto const& other) {
return somma < other.somma;
}
};
vector<pair<int,int>>Ore; //vettore contenente (tempo in cui posso mangiare,quanto ho mangiato) di tutte le combinazioni
int binarysearch(int val){ //ritorna indice del valore minore/uguale più a destra oppure -37 se non esiste
int l=0,r=Ore.size(),mid,left=-37;
while(l<=r){
mid=((l+r)/2);
if(Ore[mid].first==val){ //trovo il numero, non serve più cercare
return mid;
}
if(Ore[mid].first<val){ //trovo un numero più piccolo cerco a destra
left=mid; //salvo questo indice, in caso fosse il più piccolo che trovo
l=mid+1;
}else{ //trovo un numero più grande cerco a sinistra
r=mid-1;
}
}
return left; //il numero ritornato sarebbe -37 in caso non avessi trovato nessun cibo che finisco di mangiare prima di quello attuale
}
int main(){
ifstream cin("input.txt");
int N,ini,fin,peso;
cin>>N;
vector<piatto>P; //vettore in cui salvo i piatti in ordine di fine
piatto tmp;
for(int i=0;i<N;i++){
cin>>ini>>peso>>fin;
tmp.peso=peso; //quanto vale il piatto
tmp.inizio=ini; //quando inizio a mangiare
tmp.somma=(ini+fin); //quando finisco di mangiare il piatto
P.push_back(tmp);
}
sort(P.begin(),P.end()); //ordino i piatti a seconda di quando li finisico
for(int i=0;i<N;i++){
if(Ore.size()==0){ //sono al primo piatto, non posso aver mangiato nulla prima
Ore.push_back({P[i].somma,P[i].peso});
}else{
//devo trovare quanto ho mangiato finora nel migliore dei casi, l'elemento più a destra minore/uguale ad inizio
int val=0,indx=binarysearch(P[i].inizio);
if(indx!=-37){//attenzione se non trovo questo elemento!! (significa che non ho finitò piatti prima dell'arrivo di questo)
val=Ore[indx].second; //la soluzione fino al tempo in cui arriva il piatto
}
val+=P[i].peso; //mangio il piatto
if(Ore[Ore.size()-1].first==P[i].somma){ //potrei finire due piatti nello stesso momento, cosa mi conviene fare?
Ore[Ore.size()-1].second=max((val),Ore[Ore.size()-1].second);
}else{
if(val>Ore[Ore.size()-1].second){ //la soluzione di prima non mi conviene
Ore.push_back({(P[i].somma),(val)});
}
}
}
}
cout<<Ore[Ore.size()-1].second;
//la soluzione si trova sicuramente nell'ultima posizione,
//in quanto se per un tempo in cui finisco un piatto esiste una soluzione migliore non verrà cambiato nulla
return 0;
}
Grazie per l’aiuto