Ciao a tutti,
ho risolto il problema forgotten pencil case con questo semplice algoritmo:
#include <fstream>
#include <iostream>
using namespace std;
int minStud(int[],int,int);
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
int num;
in >> num; //totale da pagare
int studenti[num];
int noPencil=0;
for(int i=0;i<num;i++)
{
int a;
in>>a;
if(a==0) noPencil++;
studenti[i]=a;
}
int min=minStud(studenti,num,noPencil);
out << min << endl;
in.close();
out.close();
}
int minStud(int v[],int l,int noPencil)
{
if(v[0]==0&&v[1]>1)
{
v[0]++;
v[1]--;
noPencil--;
}
for(int i=1;i<l-1;i++)
{
if(v[i]==0)
{
if(v[i-1]>1)
{
v[i-1]--;
v[i]++;
noPencil--;
}else if(v[i+1]>1)
{
v[i+1]--;
v[i]++;
noPencil--;
i++;
}
}
}
if(v[l-1]==0&&v[l-2]>1) noPencil--;
return noPencil;
}
che segue un banale approccio Greedy.
Ottengo però 95% sbagliando 2 test case.
Qualcuno ha qualche suggerimento?
Grazie