Pagini recente » Cod sursa (job #2668231) | Cod sursa (job #940559) | Cod sursa (job #2641894) | Cod sursa (job #928220) | Cod sursa (job #463275)
Cod sursa(job #463275)
//NEGACEVSCHI VLADIMIR-ALEXANDRU
//GRUPA 324 CA
#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);
// 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 numarul maxim de
// gutui pe care le-as fi putut culege pana la gutuia analizata
// este egal cu numarul de gutui culese 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);
}
// daca numarul maxim de gutui pe care le-as fi putut culege
// pana la gutuia analizata nu este egal cu numarul de gutui
// culese atunci..
else if((ch - h)/u != (ch - it2->inaltime + u)/u){
// adaug gutuia analizata in cos
cos.push_back(*it2);
push_heap(cos.begin(), cos.end(), comp2);
if(h - u < 0)
h = 0;
else
h -= u; // inaltimea la care pot ajunge scade
// cu u
}
}
// scriu in fisierul de iesire greutatea cosului
rezultat(cos, out);
free(aux);
fclose(in);
fclose(out);
return 0;
}