Pagini recente » Cod sursa (job #2708180) | Cod sursa (job #3212369) | Cod sursa (job #1166401) | Cod sursa (job #2772547) | Cod sursa (job #465887)
Cod sursa(job #465887)
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
const double eps = 0.0000001;
//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;
long double h1, h2, dif1, dif2;
long double sum;
double a, b, rec;
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(d[i]);
//printf ("%d\n", d[i]);
//H2.push(mp(d[i], i));
}
//printf ("%lf\n", sum);
while (fabs (sum - rec) > eps && sum > rec)
{
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)
{
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;
}