Cod sursa(job #440306)

Utilizator razielRazvan Madalin Oita raziel Data 11 aprilie 2010 23:39:17
Problema Gutui Scor 40
Compilator cpp Status done
Runda teme_upb Marime 3.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

struct gutuie {
    unsigned int height;
    unsigned int weight;
};

//clasa comparator folosita la ordonarea vectorului de gutui dupa inaltimea si greutate
class compare {
    int hmax, nivel;
public:
    compare(int i, int j) : hmax(i), nivel(j) {};
    bool operator()(gutuie x, gutuie y) {
        return (((hmax - x.height) / nivel) + 1 < ((hmax - y.height) / nivel) + 1)
                || (!(((hmax - y.height) / nivel) + 1 < ((hmax - x.height) / nivel) + 1) && (x.weight > y.weight));
    }
};

bool operator < (gutuie a, gutuie b) {
	return a.height > b.height;
}

int main() {
    int n;
    unsigned int h, u;
    gutuie g;
    vector<gutuie> gutui;
    vector<int> nivel;
    //priority queue care satisface proprietatea de min-heap
    priority_queue< int, vector<int>, greater<int> > best;

    //citirea datelor de intrare
    ifstream fin("gutui.in");
    fin >> n >> h >> u;
    for (int i = 0; i < n; i++) {
        fin >> g.height >> g.weight;
        gutui.push_back(g);
    }
    fin.close();

    //ordonam vectorul de gutui dupa inaltime si greutate
    sort(gutui.begin(), gutui.end());

    //construim vectorul nivel care contine pt fiecare gutuie nivelul pe care se afla
    for (int i = 0; i < n; i++)
        nivel.push_back(((h - gutui[i].height) / u) + 1);
    nivel.push_back(nivel[n - 1] + 1);

    int i = 0;
    int niv = nivel[0];
    int ad = 0;
    //pt fiecare gutuie
    while (i < n) {
        //daca este pe nivelul curent si nu am adaugat maximul posibil de gutui
        if (nivel[i] == niv && ad < niv) {
            //adaugam gutuia in p_queue
            best.push(gutui[i].weight);
            ad++;
			if (best.size() > niv) {
				best.pop();
			}
            //daca urmatoarea gutuie e pe un nivel mai mare
            if (nivel[i + 1] > niv) {
                //trunchiem vectorul la numarul maxim de gutui care se pot adauga de pe nivelul curent
                /*while (best.size() > niv) {
                    best.pop();
                }*/
                //incrementam nivelul curent
                niv = nivel[i + 1];
                ad = 0;
            }
            i++;
        }
        //daca este pe nivelul curent dar am adaugat maximul posibil de gutui deja
        else if (nivel[i] == niv && ad == niv) {
            //facem aceeasi verificare ca mai sus si trecem mai departe
            if (nivel[i + 1] > niv) {
                /*while (best.size() > niv) {
                    best.pop();
                }*/
                niv = nivel[i + 1];
                ad = 0;
            }
            i++;
        }
    }

    //calculam greutatea maxima
    unsigned int gmax = 0;
    while (best.size() > 0) {
        gmax += best.top();
        best.pop();
    }

    //afisam
    ofstream fout("gutui.out");
    fout << gmax << endl;
    fout.close();

    return 0;
}