Cod sursa(job #440057)

Utilizator daniel.pleteaPletea Daniel daniel.pletea Data 11 aprilie 2010 21:41:08
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.45 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <vector>

using namespace std;   //pentru folosirea heap-ului

FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,rest;
long long int max_weight;

typedef struct {
   int height;      //structura gutuie ce contine inaltimea si greutatea
   int weight;
} gutuie;

gutuie tree[100001];  //vector de gutui

int compare (const void * a, const void * b)
{
  //functie de comparatie
  //pentru a ordona crescator
  return ( (*(gutuie*)a).height - (*(gutuie*)b).height );  //gutuile dupa inaltime
}

main() {
    int i, j;
    vector<int> coll;
    make_heap (coll.begin(), coll.end());
    
    fs = fopen("gutui.in","r");
    fd = fopen("gutui.out","w");
    
    if (fs==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    if (fd==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    fscanf(fs,"%i",&N);             //citeste numarul de gutui 
    fscanf(fs,"%i",&max_height);    //citeste inaltimea maxima
    fscanf(fs,"%i",&height_inc);    // citeste inaltime cu care se ridica celelalte gututi 
                                    // cand se culege una
    rest = max_height%height_inc;       
    max_height=max_height/height_inc;    // calculeaza inaltime/inaltime_ridicare
    for(i=0;i<N;i++){
       fscanf(fs,"%i",&x);    //citeste inaltimile
       if(x%height_inc>rest)
          tree[i].height = x / height_inc + 1;  //scaleaza inaltimile la pasul de creste a inaltimilor
       else                                      // adica height_inc
          tree[i].height = x / height_inc;
       fscanf(fs,"%i",&x);
       tree[i].weight = x;           //greutate
    }
    
    j=0;
    max_weight=0;
    qsort(tree,N,sizeof(gutuie),compare);  //o sortare dupa inaltime;
    for(i=tree[0].height;i<=max_height;i++)  //parcurgem
    {
       while(i == tree[j].height){           // si la fiecare pas alegem un maxim 
         coll.push_back (tree[j].weight);      //din toate greutatile din heap
         push_heap (coll.begin(), coll.end());
         j++;        
       }
       if(coll.size()>0){
          max_weight = max_weight + coll.front();  //treb verif si ca heap-ul sa aiba ceva
          pop_heap(coll.begin(), coll.end());
          coll.pop_back();
       }
    }  
    
    fprintf(fd,"%lli",max_weight);  //scrie in fisier greutatea
    
    fclose(fs);
    fclose(fd);
    return 0;
}