Pagini recente » Cod sursa (job #2392961) | Cod sursa (job #1018499) | Cod sursa (job #2944188) | Cod sursa (job #195811) | Cod sursa (job #436298)
Cod sursa(job #436298)
/*
======================== TEMA 1 PA =========================
===Problema 2 - Gutui===
Student : PALITA FLORIAN
GRUPA : 324 CC
=============================================================
*/
#include <iostream>
#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 {
int greutati[10000];
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
int g_gutui[100000]; //Vector cu greutatile gutuilor
int marcaje[100000]; //Vector cu marcaje ( 1-daca gutuia e pe nivelul actual , 0-daca nu )
int n_gutui[100000]; //Vector cu nivelul pe care e gutuia
//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, j = 0;
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);
marcaje[i] = 0;
g_gutui[j] = p[i].greutate;
j++;
}
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[nivele[numar_nivele].lung] = g_gutui[i];
n_gutui[i] = numar_nivele;
nivele[numar_nivele].lung++;
}
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[nivele[numar_nivele].lung] = g_gutui[i];
n_gutui[i] = numar_nivele;
nivele[numar_nivele].lung++;
}
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[nivele[numar_nivele].lung] = g_gutui[i];
n_gutui[i] = numar_nivele;
nivele[numar_nivele].lung++;
}
numar_nivele++;
}
for (i = 0 ; i < numar_nivele ; i++)
qsort(nivele[i].greutati, nivele[i].lung, sizeof(int), compare);
}
//Functie care sterge primul nivel , dupa culegerea unei gutui
void stergeNivel() {
int i, j;
for (i = 1 ; i < numar_nivele ; i++) {
nivele[i-1].lung = nivele[i].lung;
for (j = 0 ; j < nivele[i-1].lung ; j++)
nivele[i-1].greutati[j] = nivele[i].greutati[j];
}
numar_nivele--;
for (i = 0 ; i < N ; i++)
n_gutui[i]--;
}
int main() {
int i, u = 0, j, contor = 1, nr;
int culese[100000],culese2[100000];
input_data();
partition();
nr = numar_nivele;
//printf("NUMAR NIVELE : %d\n",nr);
while (numar_nivele > 0) {
//Daca nu e nicio gutuie pe nivel
if (nivele[0].lung == 0) {
contor++; //Pot culege inca o gutuie
//printf("CONTOR %d\n",contor);
}
else {
//Culeg cate gutui am voie si le pun in vectorul culese
for (i = 0 ; i < contor ; i++) {
if ((nivele[0].lung - i) <= 0) {
contor = contor - i + 1;
break;
}
else {
culese[u] = nivele[0].greutati[i];
u++;
}
}
qsort(culese, u, sizeof(int), compare);
if (u > nr - numar_nivele + 1)
u = nr - numar_nivele + 1;
/*printf("CONTOR %d\n",contor);
printf("CULESE : \n");
for (j = 0 ; j < u ; j++)
printf("%d ",culese[j]);
printf("\n");
printf("CULESE2 : \n");
for (j = 0 ; j < i - 1; j++)
printf("%d ",culese2[j]);
printf("\n");
sort (culese,culese+u);
sort (culese2,culese2+i-1);
vector<int> v(u+i-1);
copy (culese,culese+u,v.begin());
copy (culese2,culese2+i-1,v.begin()+u);
inplace_merge (v.begin(),v.begin()+u,v.end(),comp2);
if ((int)v.size() > (nr - numar_nivele + 1)) {
v.resize(nr - numar_nivele + 1);
printf("VECTOR MARE\n");
for (j = 0 ; j < nr - numar_nivele + 1 ; j++) {
culese[j] = v[j];
printf("%d ",culese[j]);
}
printf("\n");
printf("AJUNGE\n");
u = nr - numar_nivele + 1;
}
else
u = (int)v.size();*/
}
stergeNivel();
}
int S = 0;
for (i = 0 ; i < u ; i++)
S += culese[i];
g = fopen("gutui.out", "w");
fprintf(g, "%d\n", S);
fclose(g);
return 0;
}