Pagini recente » Cod sursa (job #1872549) | Cod sursa (job #2447585) | Cod sursa (job #2105201) | Cod sursa (job #2198074) | Cod sursa (job #488294)
Cod sursa(job #488294)
#include <fstream>
#include <algorithm>
using namespace std;
typedef struct{
double v,s;
} elem;
elem a[100005];
int n,heapsize,k=0;
double r,suma,A,B;
void heapify(int i)
{
int right,largest,left;
largest=i;
left=i*2; right=i*2+1;
if(left<=heapsize and a[left].s>a[i].s) largest=left;
if(right<=heapsize and a[right].s>a[largest].s) largest=right;
if(largest!=i) { swap(a[i],a[largest]); heapify(largest); }
}
void buildheap(void)
{
int i;
for(i=heapsize/2+1;i>0;i--) heapify(i);
}
void extractmax(void)
{
suma-=a[1].s;
a[1].s=a[1].v-(a[1].v*B);
a[1].v*=B;
heapify(1);
}
void solve(void)
{
while(suma>r)
{
k++;
extractmax();
}
}
int main()
{
int i;
ifstream fi("minim2.in");
ofstream fo("minim2.out");
fi>>n;
suma=0;
for(i=1;i<=n;i++) fi>>a[i].v,suma+=a[i].v;
fi>>A>>B>>r;
for(i=1;i<=n;i++) a[i].s=a[i].v-(a[i].v*A),a[i].v*=A;
heapsize=n;
buildheap();
solve();
fo<<k;
return 0;
}