Pagini recente » Cod sursa (job #2243862) | Cod sursa (job #606642) | Cod sursa (job #2939054) | Cod sursa (job #3190559) | Cod sursa (job #465657)
Cod sursa(job #465657)
#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 a, b, rec, h1, h2, dif1, dif2;
long double sum;
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;
}