Cod sursa(job #465656)

Utilizator TerminatorHasta La Vista Terminator Data 25 iunie 2010 11:17:37
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.35 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
const double eps = 0.000001;
//const int MAXN = 100005;
#define MAXN 100005
#define mp make_pair
#define f first
#define s second
using namespace std;

priority_queue <double> H1, H2;

int n, d[MAXN], i, step;
double sum, a, b, rec, h1, h2, dif1, dif2;
int main ()
{
	freopen ("minim2.in", "r", stdin);
	freopen ("minim2.out", "w", stdout);
	scanf ("%d\n", &n);
	for (i = 1; i <= n; i++)
		scanf ("%d", d + i);
	scanf ("%lf %lf %lf", &a, &b, &rec);
	
	for (i = 1; i <= n; i++)
	{
		sum += d[i];
		H1.push((double)d[i]);
		//printf ("%d\n", d[i]);
	       	//H2.push(mp(d[i], i));
	}
	//printf ("%lf\n", sum);
	while (sum - rec >= eps)
	{
		if (H1.size ())
		{
			dif2 = -1000000;
			h1 = H1.top (); h1 *= a;
			if (H2.size ())
			{
				h2 = (H2.top ()) * b;
				dif2 = H2.top () - h2;
			}
			//if (step == 2) printf ("%lf %lf\n", h1, h2);
			dif1 = (H1.top () - h1); 
			if (dif1 - dif2 >= eps)
			{	
				sum -= (H1.top () - h1);
				H1.pop ();
				H2.push(h1);
			//	printf ("*%lf\n", h1);
			}
			else 
			{	
				sum -= (H2.top () - h2);
				H2.pop ();
				H2.push (h2);
			//	printf ("**%lf\n", h2);
			}
		} else
		{	h2 = H2.top () * b;
			sum -= (H2.top () -h2) ;
			H2.pop ();
			H2.push (h2);
			printf ("***");
		}
		++step;
		//printf ("sum : %lf\n", sum);
	}
	printf ("%d\n", step);
	return 0;
}