Sto provando a risolvere il problema acquisti, il mio codice prevede la creazione di due vettori di somme prefisse sp e n che contengono rispettivamente i pesi e il numero degli oggetti con un peso <= i. tramite una ricerca binaria individuo qual é il peso piú alto (lo nel codice) per cui posso portare tutti gli oggetti con peso <= ad esso, dopodiché calcolo quanti oggetti di peso lo+1 posso aggiungere.
La soluzione peró da solo 32/100 e non me ne viene in mente una meno dispendiosa e non ci ho trovato errori particolari
#include <vector>
using namespace std;
vector<long long> calcola(int T, int M, vector<long long> S, vector<long long> P) {
vector<long long> R(M);
vector<long long> sp(T);
vector<long long> n(T);
sp[0]=0;
n[0]=S[0];
for(int i=1;i<T;i++){
sp[i]=sp[i-1]+S[i]*i;//peso di tutti gli oggetti fino al peso i
n[i]=n[i-1]+S[i]; //numero totale di oggetti fino al peso i
}
for (int i = 0; i < M; i++) {
int c=0;
int lo=0;
int hi=T-1;
if (P[i]>sp[T-1]){ //abbiamo piú capacitá del peso totale degli oggetti,quindi possiamo portarli tutti
c=n[T-1];
}else{
while (lo+1<hi){ //ricerca binaria per trovare fino a quale peso posso portare tutti gli oggetti piú leggeri
int mid=(lo+hi)/2;
if (P[i]>sp[mid]){
lo=mid;
}else{
hi=mid;
}
}
c+=n[lo]; //posso portare tutti gli oggetti di peso <= lo, quindi li aggiungo
c+=(P[i]-sp[lo])/(lo+1); //quanti oggetti posso portare di peso lo+1?
}
R[i] = c;
}
return R;
}