Cpp greedy solution


#1

vector Solution::solve(int a, vector &b) {
int i,n=b.size(),mn=INT_MAX;
vector v;
if(n==0)
return v;
int mni=n+1;
for(i=0;i<n;i++){
if(b[i]<mn){
mn=b[i];
mni=i;
}
}
int mx=(a/mn);
for(i=0;i<mx;i++)
v.push_back(mni);
if(!(a%mn)){
return v;
}
int diff=a-(mn*mx),k=0;
i=0;
while(diff>0 && i<mni && k<v.size()){
if((b[i]-mn)<=diff){
v[k++]=i;
diff-=(b[i]-mn);
}
else
i++;
}
return v;
}