Pagini recente » Cod sursa (job #1940278) | Cod sursa (job #520158) | Cod sursa (job #1573296) | Cod sursa (job #673683) | Cod sursa (job #463541)
Cod sursa(job #463541)
/* 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;
}