Cod sursa(job #488294)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 28 septembrie 2010 09:33:24
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#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;
}