Cod sursa(job #2253612)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 4 octombrie 2018 10:42:32
Problema Minim2 Scor 40
Compilator cpp Status done
Runda shimulare_fara_shim Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("minim2.in");
ofstream out("minim2.out");
const int maxn = 100005;
priority_queue <double> pq1;
priority_queue <double> pq2;
int main()
{
    int n;
    in >> n;
    double act = 0;
    for(int i = 1; i <= n; i++)
    {
        double x;
        in >> x;
        act = act + x;
        pq1.push(x);
    }
    double a, b, record;
    in >> a >> b >> record;
    int nr = 0;
    while(act >= record)
    {
        //cerr << act << " ";
        if(pq1.empty())
        {
            int p2 = pq2.top();
            pq2.pop();
            pq2.push(p2 * b);
            act = act - p2 + p2 * b;
        }
        else if(pq2.empty())
        {
            int p1 = pq1.top();
            pq1.pop();
            pq2.push(p1 * a);
            act = act - p1 + p1 * a;
        }
        else
        {
            double p1 = pq1.top();
            double p2 = pq2.top();
            if(p1 - p1 * a > p2 - p2 * b)
            {
                pq1.pop();
                pq2.push(p1 * a);
                act = act - p1 + p1 * a;
            }
            else
            {
                //cerr << "  " << p1 << " " << p2 << "  ";
                pq2.pop();
                pq2.push(p2 * b);
                act = act - p2 + p2 * b;
            }
        }
        //cerr << act << "\n";
        nr++;
    }
    out << nr << "\n";
    return 0;
}