Pagini recente » Cod sursa (job #2631556) | Cod sursa (job #1857994) | Cod sursa (job #1460896) | Cod sursa (job #1509074) | Cod sursa (job #465942)
Cod sursa(job #465942)
#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;
}