Cod sursa(job #463541)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 16 iunie 2010 13:37:42
Problema Gutui Scor 90
Compilator cpp Status done
Runda teme_upb Marime 3.35 kb
/* Rafailescu Marius 322CA */
#include <stdio.h>  
#include <stdlib.h>  
#include <fstream>
#include <string.h>
using namespace std;

//structura asociata unei gutui
typedef struct {
	int h;
	int g;
}gutuie;

// merge - interclaseaza 2 vectori
void merge(int starts, int startd, int stopd, gutuie *a){  
	int n = stopd - starts + 1;  
	int is = starts, id = startd, stops = startd - 1, it = 0, i;  
	gutuie *temp = (gutuie*)malloc(n * sizeof(gutuie));  
   
	while(is <= stops && id <= stopd) { 
		if (a[is].h < a[id].h){
			temp[it].h = a[is].h;
			temp[it++].g = a[is++].g;
		}
		else if (a[is].h > a[id].h){
			temp[it].h = a[id].h;
			temp[it++].g = a[id++].g;
		}  else{ //egale
			if (a[is].g < a[id].g){
				temp[it].h = a[is].h;
				temp[it++].g = a[is++].g;
			}
			else {
				temp[it].h = a[id].h;
				temp[it++].g = a[id++].g;
			}
		}
	}
	while (is <= stops){
		temp[it].h = a[is].h;
		temp[it++].g = a[is++].g;
	}
	while (id <= stopd){
		temp[it].h = a[id].h;
		temp[it++].g = a[id++].g;
	}   
	  
	for (i = 0; i < n; i++){
		a[starts+i].h = temp[i].h;
		a[starts+i].g = temp[i].g;
	}
	free(temp);  
}  

// Merge Sort   
void MS(int s, int d, gutuie *a){  
if (s < d)  
    {  
    int m = (s + d) / 2;  
    MS(s, m, a);  
    MS(m+1, d, a);  
    merge(s, m+1, d, a);  
    }  
}  
  
void MergeSort(int n, gutuie *a){  
    MS(0, n-1, a);  
}

// functie ce intoarce pozitia pe care se afla minimul dintr-un vector
int pcmpa(int *v, int n){
	int minim,p,c;
	minim = v[0];
	p = 0;
	for (c = 1; c < n; ++c){
		if (minim == 0) return p;
		if (v[c] < minim){
			minim = v[c];
			p = c;
		}
	}
	return p;
}  
   
int main(){  
int n, h, u, i, max = 0, j, *best, *sbest, ch, k, niv = 0, poz;  
ifstream in ("gutui.in");// deschidere fisier de intrare
ofstream out ("gutui.out");// deschidere fisier de iesire
in >> n; in >> h; in >> u;// citire date de intrare(dimensiunile problemei)
gutuie *v = (gutuie*)calloc(n, sizeof(gutuie));
best = (int*)calloc((h / u) + 2, sizeof(int)); 
sbest = (int*)calloc(u + 1, sizeof(int)); 
for (i = 0; i < n; ++i){ // citire date de intrare (gutuile)
	in >> v[i].h; 
	in >> v[i].g;
}
in.close();// inchidere fisier de intrare
MergeSort(n,v);// sortare vector de gutui

while (niv <= (h - v[0].h) / u){// cat timp mai exista niveluri pe care nu le-am vizitat
	k = 0;
	max = 0;
	ch = 0;
	memset(sbest, 0x00, sizeof sbest);// initializez cu 0 s(econd)best
	for (j = n-1; j >= 0; --j){
		if (v[j].h <= h - niv * u) 		
		{
			if (v[j].h >= h - (niv + 1) * u + 1)// dc e cuprins in nivelul curent
			{
				if (max < v[j].g){// retin greutatea maxima de pe nivelul curent in best, iar celelalte greutati se retin in sbest
					max = v[j].g;
					if (best[niv] == 0) best[niv] = max;
					else{
						sbest[ch++] = best[niv];
						best[niv] = max;
					}
				}
				else{
					sbest[ch++] = v[j].g;
				}
			}
			else break;
		}
	}
	// acum verific daca nu cumva o greutate de la nivelul curent
	// e mai mare decat cea mai proasta alegere facuta pana atunci
	// daca da, atunci fac interschimbul
	if (ch) poz = pcmpa(best, niv);
	for (i = 0;i < ch && k < niv; ++i){
		if (sbest[i] > best[poz]){
			best[poz] = sbest[i];
			++k;
			if (i != ch-1) poz = pcmpa(best, niv);
		}
	}
	++niv;
}
max = best[0];
for (i = 1; i < niv; ++i) max += best[i];// calculez greutatea gutuilor culese
out << max;// o scriu in fisierul de iesire
out.close();// inchid fisierul de iesire
free(v);
return 0;  
}