Pagini recente » Cod sursa (job #1521759) | Cod sursa (job #1311626) | Cod sursa (job #1785910) | Cod sursa (job #1515908) | Cod sursa (job #439174)
Cod sursa(job #439174)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct {
unsigned int greutate;
unsigned int inaltime;
} gutuie;
bool comp1(gutuie g1, gutuie g2){
return (g1.inaltime > g2.inaltime);
}
bool comp2(gutuie g1, gutuie g2){
return (g1.greutate > g2.greutate);
}
void rezultat(vector<gutuie> g, FILE *f){
vector<gutuie>::iterator it;
unsigned long long int total = 0;
for(it = g.begin(); it != g.end(); it++)
total += it->greutate;
fprintf(f, "%lld", total);
}
int main(){
FILE *in = fopen("gutui.in", "r");
FILE *out = fopen("gutui.out", "w");
unsigned int n,h,u,i;
fscanf(in, "%d %d %d", &n, &h, &u);
unsigned int ch = h;
vector<gutuie> gut, cos;
vector<gutuie>::iterator it;
vector<gutuie>::iterator it2;
gutuie g;
char *aux = (char*) malloc (100 * sizeof(char));
fgets(aux, 100, in); // sar peste linia curenta
for(i = 0; i < n; i++){
fscanf(in, "%d %d", &g.inaltime, &g.greutate);
gut.push_back(g);
fgets(aux, 100, in); //sar peste linia curenta
}
// sortez descrescator vectorul de gutui dupa inaltime
sort(gut.begin(), gut.end(), comp1);
for(it = gut.begin(); it != gut.end(); it++){
if(it->inaltime <= h){ // daca pot ajunge la gutuie
cos.push_back(*it); // atunci o adaug in cos
// in loc sa adaug U cm la inaltimea fiecarei gutui in parte de
// fiecare data cand culeg o gutuie, voi scadea U cm din inaltimea
// maxima la care pot ajunge (h)
if(h - u < 0) // conditie pusa din cauza ca h si u sunt
h = 0; // unsigned int
else
h -= u; // inaltimea maxima la care pot ajunge
// scade cu U cm
}
else
break;
}
// daca am reusit sa culeg toate gutuile atunci afisez greutatea cosului
if(gut.size() == cos.size()){
rezultat(cos, out);
return 0;
}
// fac un minheap al cosului ordonat dupa greutati
make_heap(cos.begin(), cos.end(), comp2);
//h = ch; // TODO pentru varianta lui Vali asta trebuie comentat
// acum analizez gutuile care n-au intrat in cos
for(it2 = it; it2 != gut.end(); it2++){
// daca greutatea gutuii analizate este mai mare decat greutatea
// celei mai usoare gutui din cos --SI-- daca nu pot ajunge la
// gutuia analizata, dar ea este cu cel mult u cm mai sus decat
// pot ajunge eu atunci...
if(it2->greutate > cos.front().greutate && (ch-h)/u == (ch-it2->inaltime+u)/u ){
// pun in locul celei mai usoare gutui din cos pe gutuia
// analizata si actualizez minheap-ul
pop_heap(cos.begin(), cos.end(), comp2);
cos.pop_back();
cos.push_back(*it2);
push_heap(cos.begin(), cos.end(), comp2);
/*cos.front() = *it2;
sort_heap(cos.begin(), cos.end(), comp2);*/
}
//daca pot ajunge la gutuie atunci...
else if(it2->inaltime <= h){
// adaug gutuia analizata in cos
cos.push_back(*it2);
push_heap(cos.begin(), cos.end(), comp2);
if(h - u < 0) //TODO
h = 0; //TODO
else //TODO
h -= u; // inaltimea la care pot ajunge scade //TODO
// cu u
}
}
// scriu in fisierul de iesire greutatea cosului
rezultat(cos, out);
free(aux);
fclose(in);
fclose(out);
return 0;
}