Pagini recente » Cod sursa (job #2221792) | Cod sursa (job #2317085) | Cod sursa (job #2631844) | Cod sursa (job #1686032) | Cod sursa (job #465940)
Cod sursa(job #465940)
#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;
}