Pagini recente » Cod sursa (job #1660692) | Cod sursa (job #1447421) | Cod sursa (job #1320285) | Cod sursa (job #556099) | Cod sursa (job #436375)
Cod sursa(job #436375)
/*
======================== 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 care retine pentru o gutuie inaltimea si greutatea
typedef struct gutui {
int inaltime;
int greutate;
} gutui;
//Structura unui nivel din copac
typedef struct niv {
vector<int> greutati;
int lung;
} 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
gutui p[100000]; //Vector cu cele N perechi inaltime - greutate
niv nivele[10000]; //Vector cu nivelele gutuiului
int numar_nivele = 0; //Numarul de nivele
//Functia de comparare pentru qsort
int compare (const void * a, const void * b) {
return ( *(int*)b - *(int*)a );
}
//Functia de compare pentru interclasare
bool comp2(unsigned int a, unsigned int b) {
return a > b;
}
//Functie pentru preluarea datelor din fisierul de intrare
void input_data() {
FILE *f;
int i;
f = fopen("gutui.in", "r");
fscanf(f, "%d %d %d\n", &N, &H, &U);
for (i = 0 ; i < N ; i++)
fscanf(f, "%d %d\n", &p[i].inaltime, &p[i].greutate);
fclose(f);
}
//Functie ce partitioneaza pe nivele gutuile
void partition() {
int inf, sup, i;
sup = H;
inf = H - U;
while (inf > 0) {
nivele[numar_nivele].lung = 0;
for (i = 0 ; i < N ; i++)
if ((p[i].inaltime > inf) && (p[i].inaltime <= sup)) {
nivele[numar_nivele].greutati.push_back(p[i].greutate);
nivele[numar_nivele].lung++;
}
sort(nivele[numar_nivele].greutati.begin(), nivele[numar_nivele].greutati.end(), comp2);
numar_nivele++;
sup = inf;
inf = inf - U;
}
if (inf == 0) {
nivele[numar_nivele].lung = 0;
for (i = 0 ; i < N ; i++)
if ((p[i].inaltime > inf) && (p[i].inaltime <= sup)) {
nivele[numar_nivele].greutati.push_back(p[i].greutate);
nivele[numar_nivele].lung++;
}
sort(nivele[numar_nivele].greutati.begin(), nivele[numar_nivele].greutati.end(), comp2);
numar_nivele++;
}
if (inf < 0) {
nivele[numar_nivele].lung = 0;
for (i = 0 ; i < N ; i++)
if ((p[i].inaltime >= 0) && (p[i].inaltime <= sup)) {
nivele[numar_nivele].greutati.push_back(p[i].greutate);
nivele[numar_nivele].lung++;
}
sort(nivele[numar_nivele].greutati.begin(), nivele[numar_nivele].greutati.end(), comp2);
numar_nivele++;
}
}
int main() {
int i, contor, k, S = 0;
vector<int> culese;
input_data();
partition();
for (k = 0 ; k < numar_nivele ; k++) {
contor = k + 1;
if (nivele[k].lung != 0) {
for (i = 0 ; i < contor ; i++)
if ((nivele[k].lung - i) <= 0)
break;
else
culese.push_back(nivele[k].greutati[i]);
inplace_merge(culese.begin(), culese.end() - i, culese.end(), comp2);
culese.resize(contor);
}
}
for (i = 0 ; i < (int)culese.size() ; i++)
S += culese[i];
//printf("%d\n",S);
g = fopen("gutui.out", "w");
fprintf(g, "%d\n", S);
fclose(g);
return 0;
}