Pagini recente » Cod sursa (job #1120221) | Cod sursa (job #2038705) | Cod sursa (job #463196) | Cod sursa (job #2960419) | Cod sursa (job #463147)
Cod sursa(job #463147)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
/******************************************************************************
* *
* sortW() - functie auxiliara pentru compararea elementelor *
* de pe pozitia a doua din pereche *
* *
******************************************************************************/
bool sortW(pair<unsigned int,unsigned int>x,pair<unsigned int,unsigned int>y) {
return(x.second > y.second);
}
/******************************************************************************
* *
* sortH() - functie auxiliara pentru compararea elementelor *
* de pe pozitia a doua din pereche *
* *
******************************************************************************/
bool sortH(pair<unsigned int,unsigned int>x, pair<unsigned int, unsigned int>y) {
return(x.first > y.first);
}
int main(){
unsigned int n; // nr de gutui
unsigned int h; // inaltimea maxima
unsigned int prag; // inaltimea cu care se inalta ramurile
unsigned int pr = 0; // inaltimea curenta cu care se inalta ramurile
unsigned int x,y; // variabile pentru a crea perechile
vector< pair<unsigned int,unsigned int> > gutui;// vectori de perechi pentru inaltimi si greutati
vector< pair<unsigned int,unsigned int> > cules;// greutatea fiecarei gutui culese
pair<unsigned int,unsigned int> k ; // lungimea vectorului cules[]
unsigned int i; // variabile auxiliare
FILE *f, *g;
f = fopen("gutui.in","r");
g = fopen ("gutui.out","w");
/* citire date de unsigned intrare */
fscanf(f,"%d %d %d", &n, &h, &prag);
gutui.resize(n);
for(i = 0; i<n; i++){
fscanf(f, "%d %d",&x,&y);
gutui[i] = make_pair(x,y);
}
sort(gutui.begin(), gutui.end(), sortH);
make_heap(cules.begin(),cules.end());
unsigned int len = gutui.size();
pr = 0;
for(i = 0; i<len; i ++){
/* verificare daca Gigel poate ajunge la ramuri */
if((gutui[i].first + pr) <= h && pr <= h){
cules.push_back(gutui[i]);
push_heap(cules.begin(),cules.end(),sortW);
/* cresterea inaltimii cu care se ridica ramurile */
pr +=prag;
}
else{
/* verificare daca nu a fost aleasa o greutate mai
* usoara decat cea curenta */
if(cules.front().second < gutui[i].second){
pop_heap(cules.begin(), cules.end(),sortW);
cules.pop_back();
cules.push_back(gutui[i]);
push_heap(cules.begin(),cules.end(),sortW);
}
}
}
len = cules.size(); // retin lungimea heap-ului
unsigned int s = 0; // variabila in care se retine suma
// calculez suma greutatilor
for(i=0; i<len; i++)
s += cules[i].second;
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}