Cod sursa(job #465940)

Utilizator indestructiblecont de teste indestructible Data 25 iunie 2010 15:27:52
Problema Minim2 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 200005
#define prec 0.000001
using namespace std;
int n,op,r,ord[NMAX],poz=1,act[NMAX];
double A[NMAX],a,b,rez,fin;
struct heap
{
	double a;
	int b;
};
heap B[NMAX];
char marc[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%lf",&A[i]);
		ord[i]=i;
		rez+=A[i];
	}
	scanf("%lf%lf%lf",&a,&b,&fin);
}
void interschimba(int x,int y)
{
	double t;
	int p;
	act[B[x].b]=y; act[B[y].b]=x;
	t=B[x].a; B[x].a=B[y].a; B[y].a=t;
	p=B[x].b; B[x].b=B[y].b; B[y].b=p;
}
void urca(int nod)
{
	if (nod>1)
		if (B[nod/2].a<B[nod].a)
		{
			interschimba(nod/2,nod);
			urca(nod/2);
		}
}
void coboara(int nod)
{
	if (B[nod*2].a>B[nod].a || B[nod*2+1].a>B[nod].a)
	{
		int best=nod*2;
		if (nod*2+1<=r && B[nod*2+1].a>B[2*nod].a)
			best=nod*2+1;
		interschimba(best,nod);
		coboara(best);
	}
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
void solve()
{
	int i;
	for (i=1; i<=n; i++)
	{
		B[++r].a=A[i]; B[r].b=i;
		urca(r);
	}
	while (rez>fin)
	{
		if (!marc[B[1].b])
		{
			marc[B[1].b]=1;
			rez-=(1-a)*B[1].a;
			B[1].a=B[1].a*a;
			coboara(1);
			op++;
		}
		else
		{
			while (marc[ord[poz]] && poz+1<=r) poz++;
			if ((1-b)*B[1].a<(1-a)*A[ord[poz]])
			{
				marc[ord[poz]]=1;
				rez-=(1-a)*A[ord[poz]];
				B[act[ord[poz]]].a=B[act[ord[poz]]].a*a;
				coboara(act[ord[poz]]);
				op++;
			}
			else
			{
				rez-=(1-b)*B[1].a;
				B[1].a=B[1].a*b;
				coboara(1);
				op++;
			}
		}
		if (modul(rez-fin)<prec)
			break ;
	}
}
bool comp(int x,int y)
{
	return A[x]>A[y];
}
int main()
{
	freopen("minim2.in","r",stdin);
	freopen("minim2.out","w",stdout);
	read();
	sort(ord+1,ord+n+1,comp);
	solve();
	printf("%d\n",op);
	return 0;
}