Cod sursa(job #565370)

Utilizator crushackPopescu Silviu crushack Data 27 martie 2011 17:30:19
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>
#define NMax 100000
using namespace std;

const char IN[]="minim2.in",OUT[]="minim2.out";

ifstream fin(IN);
ofstream fout(OUT);

int N;
long double A,B,R;
struct elem{
	long double v;
	bool first;
}a[NMax];

bool cmp(elem a,elem b)
{
	if (a.first && b.first)
		return a.v-a.v*B<b.v-b.v*B;
	if (!a.first && !b.first)
		return a.v-a.v*A<b.v-b.v*A;
	if (!a.first && b.first)
		return a.v-a.v*A<b.v-b.v*B;
	return a.v-a.v*B<b.v-b.v*A;
}

int main()
{
	int i,Rez=0;
	long double S=0;
	fin>>N;
	for (i=0;i<N;++i)
		fin>>a[i].v,
		S+=a[i].v;
	fin>>A>>B>>R;
	
	make_heap(a,a+N,cmp);
	
	while (S>R)
	{
		while (S>R && cmp(a[1],a[0]) && cmp(a[2],a[0]))
		{
			++Rez;
			S-=a[0].v-a[0].v*(a[0].first ? B : A);
			a[0].v*=(a[0].first ? B : A);
			a[0].first=true;
		}
		pop_heap(a,a+N,cmp);
		push_heap(a,a+N,cmp);
	}
	
	fout<<Rez<<"\n";
	
	return 0;
}