Cod sursa(job #437808)

Utilizator vladnegaNegacevschi Vladimir-Alexandru vladnega Data 10 aprilie 2010 02:34:36
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.67 kb
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstdlib>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

typedef struct {
	int greutate;
	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;
	int total = 0;
	for(it = g.begin(); it != g.end(); it++)
		total += it->greutate;
	fprintf(f, "%d", total);
}

int main(){
	FILE *in = fopen("gutui.in", "r");
	FILE *out = fopen("gutui.out", "w");
	int n,h,u,i;
	fscanf(in, "%d %d %d", &n, &h, &u);
	
	int ch = h; //copie a lui h
	
	vector<gutuie> gut, cos;
	//vector<gutuie>::iterator it;
	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 <= ch){		// daca pot ajunge la gutuie
			cos.push_back(*it);	// atunci o adaug in cos
			ch -= 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;
	}
	
	// acum imi creez vectorul care contine gutuile care nu sunt in cos
	vector<gutuie>::iterator it2;
	for(it = cos.begin(); it != cos.end(); it++)
		for(it2 = gut.begin(); it2 != gut.end(); it2++)
			if(it2->inaltime == it->inaltime &&
			   it2->greutate == it->greutate){
			   	gut.erase(it2);
			   	break;
			}
		
	// fac un minheap al cosului ordonat dupa greutati
	make_heap(cos.begin(), cos.end(), comp2);
	*/
	/*for(it = cos.begin(); it != cos.end(); it++)
		cout << "  " << it->inaltime << "->" << it->greutate;
	*/
	cos.push_back(gut.front());
	//ch += u;
	vector<gutuie>::iterator it2;
	// acum analizez gutuile care n-au intrat in cos	
	for(it2 = gut.begin(); it2 != gut.end(); it2++){
		// daca greutatea gutuii analizate este mai mare decat greutatea
		// celei mai usoare gutui din cos atunci...
		if(it2->greutate > cos.front().greutate && it2->inaltime == (ch + u)){
			cos.front() = *it2;
			sort_heap(cos.begin(), cos.end(), comp2);
		}
		//daca mai pot baga gutui in cos
		else if(it2->inaltime <= ch){
			cos.push_back(*it2);
			push_heap(cos.begin(), cos.end(), comp2);
			ch -= u;
		}
		
	}
	
	rezultat(cos, out);
	
	free(aux);
	fclose(in);
	fclose(out);
	
	return 0;
}