Pagini recente » Cod sursa (job #362475) | Cod sursa (job #671710) | Cod sursa (job #2706026) | Cod sursa (job #786717) | Cod sursa (job #520461)
Cod sursa(job #520461)
#include <stdio.h>
double heap[100010], coef[100010];
double A, B, record, sum;
int n, count;
void buildmaxheap();
void godown(int);
void swap(double&, double&);
int main()
{
freopen("minim2.in", "r", stdin);
freopen("minim2.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%lf", &heap[i]);
sum += heap[i];
}
scanf("%lf %lf %lf", &A, &B, &record);
for(int i = 1; i <= n; ++i)
{
coef[i] = A;
}
buildmaxheap();
while(sum > record)
{
++count;
sum -= heap[1] * (1 - coef[1]);
heap[1] *= coef[1];
coef[1] = B;
godown(1);
}
printf("%d\n", count);
return 0;
}
void buildmaxheap()
{
for(int i = n / 2; i > 0; --i)
{
godown(i);
}
}
void godown(int pos)
{
int m = pos, l = 2 * pos, r = 2 * pos + 1;
if(l <= n && heap[l] * (1 - coef[l]) > heap[m] * (1 - coef[m])) m = l;
if(r <= n && heap[r] * (1 - coef[r]) > heap[m] * (1 - coef[m])) m = r;
if(pos != m)
{
swap(heap[pos], heap[m]);
swap(coef[pos], coef[m]);
godown(m);
}
}
inline void swap(double&a, double&b)
{
double temp = a;
a = b;
b = temp;
}