Cod sursa(job #2194982)

Utilizator georgiuadrianadrian georgiuadrian Data 14 aprilie 2018 20:27:47
Problema Energii Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct generator
{
    int energie,numar,cost;
    long double procent;
}sir[1006];

bool cmp (const generator x, const generator y)
{
    return x.procent > y.procent;
}


int main()
{
    ifstream f("energii.in");
    ofstream g("energii.out");
    int G,W;
    long long suma=0,cost=0;
    f>>G>>W;
    g<<fixed<<setprecision(6);
    for (int i=1; i<=G; i++)
    {
        f >> sir[i].energie >> sir[i].cost;
        sir[i].procent = (sir[i].energie + 0.0) / sir[i].cost;
        sir[i].numar = i;
        suma += sir[i].energie;
        /*g<<sir[i].numar<<" "<<sir[i].energie<<" "<<sir[i].cost<<" ";
        g<<sir[i].procent<<"\n";*/
    }
    sort (sir+1,sir+G+1,cmp);

    if (suma < W )
        g<<-1;
    else
    {
        int i = 0;
        suma = 0;
        while (suma < W)
        {
            i++;
            suma += sir[i].energie;
            cost += sir[i].cost;
        }
        if (suma == W || i == G)
            g<<cost;
        else
        {
            long long costmin = 100000000;
            suma -= sir[i].energie;
            cost -= sir[i].cost;
            while (i <= G)
            {
                if (sir[i].energie + suma >= W && sir[i].cost<costmin)
                    costmin=sir[i].cost;
                i++;
            }
            g<<cost+costmin;
        }
    }

    return 0;
}