Cod sursa(job #465942)

Utilizator darrenRares Buhai darren Data 25 iunie 2010 15:33:24
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<algorithm>
using namespace std;

const double eps = 0.0000001;

int n, sh, step, hpos[100001];
double heap[100001], act[100001], a, b, r, sum;
bool ok[100001];

void push(double v, int p)
{
	heap[++sh] = v;
	hpos[sh] = p;
	
	int son = sh, fat = sh / 2;
	while (fat != 0)
	{
		if (heap[fat] < heap[son])
		{
			swap(heap[fat], heap[son]);
			swap(hpos[fat], hpos[son]);
			
			fat /= 2;
			son /= 2;
		}
		else
			break;
	}
}

void update()
{
	int fat = 1, son = 2;
	while (son <= sh)
	{
		if (son < sh && heap[son] < heap[son + 1])
			++son;
		if (heap[fat] < heap[son])
		{
			swap(heap[fat], heap[son]);
			swap(hpos[fat], hpos[son]);
			
			fat = son;
			son *= 2;
		}
		else
			break;
	}
}

int main()
{
	ifstream fin("minim2.in");
	ofstream fout("minim2.out");
	fin >> n;
	
	for (int i = 1; i <= n; ++i)
	{
		fin >> act[i];
		sum += act[i];
	}
	fin >> a >> b >> r;
	for (int i = 1; i <= n; ++i)
	{
		push(act[i] - act[i] * a, i);
	}
	
	while (sum > r - eps)
	{
		++step;
		if (!ok[hpos[1]])
		{
			sum -= heap[1];
			act[hpos[1]] *= a;
			heap[1] = act[hpos[1]] - act[hpos[1]] * b;
			ok[hpos[1]] = true;
		}
		else
		{
			sum -= heap[1];
			act[hpos[1]] *= b;
			heap[1] = act[hpos[1]] - act[hpos[1]] * b;
		}
		
		update();
	}
	
	fout << step;
}