Ciao a tutti, stavo provando a risolvere ricarica ( Allenamento Olimpiadi Italiane di Informatica (olinfo.it) ) e ho trovato una soluzione ma mi dà solo 40/100 (ho guardato gli altri post sul forum ma hanno svolto il problema in modo diverso, quindi non so cosa io stia sbagliando):
#include <vector> #include <iostream> #include <climits> #define MAXN 100000
using namespace std;
int ricarica(int N, int M, int A[], int B[]) {
int charge=0, min=INT_MAX, used;
for(int i=0; i<N; i++)
{
int plus=B[i]-A[i]+1;
if(i==N-1)
used=M-B[N-1];
else
used=A[i+1]-B[i]-1;
//cout<<charge<<" "<<plus<<" "<<used<<endl;
charge+=plus;
charge-=used;
if(charge<=0)
{
min=std::min(charge, min);
}
}
min-=(A[0]-1); //add charge for the first minutes
min*=-1; min++; //add 1 because the phone battery cannot go under 1
//(previously we've calculated as if the battery could go to 0)
return min;
}
int A[MAXN], B[MAXN];
int main() {
int N, M, i;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>N>>M; for(i=0; i<N; i++) cin>>A[i]>>B[i];
cout<<ricarica(N, M, A, B);
return 0;
}
In pratica a ogni intervallo (che va da A[i] a A[i+1], quindi comprende una ricarica e un’uso del telefono) calcolo:
- plus (quanta energia aumenta), used (quanta ne spreca) e charge (la carica totale dopo aver aggiunto plus e sottratto used.
- Controllo se charge è sotto lo 0 (x ora controllo quando arriva a 0, la parte di non scendere sotto l’1% faccio dopo) in quel caso controllo se charge è minore di min e prendo il minimo (in pratica trovo la carica minima a cui arriva charge).
Successivamente: - Aggiungo la carica necessaria per l’intervallo (0-A[0]) che quindi permette di arrivare alla prima stazione di ricarica.
- faccio diventare min positivo e aggiungo 1 (x il problema di non scendere mai sotto l’1%).
Però questa soluzione dà solo 40/100, avete suggerimenti? Grazie mille in anticipo.
Qui sotto allego lo screen della sottoposizione.
