Pagini recente » Cod sursa (job #806337) | Cod sursa (job #2246488) | Cod sursa (job #58389) | Cod sursa (job #2129915) | Cod sursa (job #436560)
Cod sursa(job #436560)
/*
======================== TEMA 1 PA =========================
===Problema 2 - Gutui===
Student : PALITA FLORIAN
GRUPA : 324 CC
=============================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
//Structura unui nivel din copac
typedef struct niv {
vector<int> greutati;
} niv;
int N; //Numarul de gutui
int H; //Inaltimea maxima la care ajunge
int U; //Inaltimea cu care se ridica
FILE *g; //Fisier de iesire
niv nivele[10000]; //Vector cu nivelele gutuiului
int numar_nivele = 0; //Numarul de nivele
//Functia de compare pentru interclasare
bool compare(unsigned int a, unsigned int b) {
return a > b;
}
//Functie pentru preluarea datelor din fisierul de intrare si repartizarea pe nivele
void input_data() {
FILE *f;
int i, greu, inal;
f = fopen("gutui.in", "r");
fscanf(f, "%d %d %d\n", &N, &H, &U);
numar_nivele = H / U;
if ((H % U) != 0)
numar_nivele++;
for (i = 0 ; i < N ; i++) {
fscanf(f, "%d %d\n", &inal, &greu);
nivele[(H - inal) / U].greutati.push_back(greu); //Repartizez gutuia pe nivelul corespunzator
}
fclose(f);
for (i = 0 ; i < numar_nivele ; i++)
sort(nivele[i].greutati.begin(), nivele[i].greutati.end(), compare); //Sortez greutatile de pe fiecare nivel descrescator
}
int main() {
int i, j, S = 0;
vector<int> culese;
g = fopen("gutui.out", "w");
input_data(); //Fac citirea din fisier si repartizarea pe nivele
for (i = 0 ; i < numar_nivele ; i++) {
if ((int)nivele[i].greutati.size() != 0) { //Daca am gutui pe nivel
for (j = 0 ; j < i + 1 ; j++)
if (((int)nivele[i].greutati.size() - j) <= 0) //Cat timp mai am gutui
break;
else
culese.push_back(nivele[i].greutati[j]); //Le culeg
inplace_merge(culese.begin(), culese.end() - j, culese.end(), compare); //Sortez dupa greutate descrescator
culese.resize(i + 1); //Mentin primele i + 1
}
}
for (i = 0 ; i < (int)culese.size() ; i++)
S += culese[i]; //Insumez greutatile
fprintf(g, "%d\n", S);
fclose(g);
return 0;
}