Salve, sto cercando di risolvere il task Ricehub e non riesco a trovare il modo ideale per posizionare il deposito.
Per ora ho ottenuto il 55/100 posizionando il deposito a metà strada dalla prima risaia e l ultima che sto considerando.
Ho applicato la binary search sulla soluzione.
#include <bits/stdc++.h>
using namespace std;
int N,B;
vector <int> v;
bool f (int x){
int i = x - 1, j = 0;
while(i < N){
int b = B;
int place = (v[j] + v[i]) / 2;
int z = j;
while(z <= i){
b -= abs(v[z] - place);
z++;
}
//cout << b << "\n";
if(b >= 0)return true;
i++;
j++;
}
return false;
}
int main(){
ifstream fin("input.txt");
ofstream fout ("output.txt");
fin >> N >> B;
v.resize(N);
for(int i = 0; i < N; i++){
fin >> v[i];
}
int inizio = 0, fine = N,mid;
while(inizio != fine){
mid = (inizio + fine) / 2 + 1;
if(f(mid)){
inizio = mid;
}else{
fine = mid - 1;
}
}
fout << inizio;
}
Ho trovato il modo migliore per posizionare il deposito : alla mediana del range che sto esaminando.
Un altro errore che ho fatto è che il budget arriva a 2 ^ 61, quindi un intero non basta ma serve un long long.
Con questi accorgimenti sono arrivato al 70/100.
Ora devo risolvere i timeout dovuti al modo in cui calcolo il costo di ogni range, devo ancora trovare il modo ottimale.
Ciao, io questo problema l’ho risolto in un altro modo: ho utilizzato due interi L e R che spostavo lungo la strada. L e R sono gli estremi del range di rasaie che prendo (L e R compresi). Ci sono 2 casi:
- sposto R perchè aggiungendo la prossima risaia rientro comunque nel budget
- sposto L perchè, se aggiungo la prossima risaia, sforo con il budget
Inoltre all’interno del range L e R conviene posizionare il deposito in una posizione particolare: (L+R)/2 oppure (L+R+1)/2 (anche se a volte sono la stessa risaia)
Spero di essere stato chiaro.
Filippo
1 Mi Piace
Inizialmente anche io avevo pensato alle sliding windows ma non riuscivo a codificare la soluzione per qualche oscuro motivo. Leggendo i tuoi suggerimeti ci sono riuscto entrando anche nella top dei tempi,grazie 
1 Mi Piace