Cod sursa(job #466094)

Utilizator cosmyoPaunel Cosmin cosmyo Data 26 iunie 2010 00:51:45
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream.h>
#include<map>
#include<utility>
#include<stdlib.h>
long n,w;
using namespace std;
multimap<double,long,greater<double> > m;
multimap<double,long >::iterator it1,it2,it;
double inf,p,a,b,sd,x,f,s,nr,sp;
int main()
{ifstream fin("minim2.in");
  fin>>n;
  long i;
  sp=0;
  long sw;
   for(i=1;i<=n;++i)
	  { fin>>x;
        sp+=x;
        m.insert(pair<double,long>(x,0));
	  }
   fin>>a>>b>>sd;
 fin.close();
 ofstream fout("minim2.out");
  while(sp>sd)
  {it2=it1=m.begin();
   ++it2;
   f=it1->first;
   s=it1->second;
   inf=f*b;
   sw=0;
   if(s==10000)
	   m.erase(it1);
   else
   {++w;	
	   if(s==0)
		   {inf=f*a;
			m.erase(it1);
			sp-=f;
			sp+=f*a;
			m.insert(pair<double,long>(inf,s+1));
			sw=1;
			++nr;
		   }
		   else
			   if(nr<=n)
				   {for(it=it2;it!=m.end();++it)
					   if(it->second==0)
						   {if(it->first*(1-a)>f-inf)
								{sp-=it->first;
								  inf=it->first*a;
								  m.erase(it);
								  sp+=inf;
								  sw=1;
								  ++nr;
								  m.insert(pair<double,long>(inf,1));
								 }
					          break;
						   }
					}	 
	   if(sw==0)
		   {m.erase(it1);
			sp-=f;
			sp+=inf;
			m.insert(pair<double,long>(inf,s+1));
		   }
   }
  }
  fout<<w;
 fout.close();
return 0;
}