Cod sursa(job #437757)

Utilizator marina.cioceaMarina Ciocea marina.ciocea Data 10 aprilie 2010 01:19:19
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 2.16 kb
#include <iostream>
#include <list>
#include <vector>
using namespace std;

typedef struct
{
    long height, weight;
    long level;        
} Gutuie;

int compare (const void * a, const void * b)
{
    Gutuie *g1=(Gutuie *)a;
    Gutuie *g2=(Gutuie *)b;
	if(((g1->height) - (g2->height))<0)
		return -1;
    return 1;
}

bool compareH(Gutuie a, Gutuie b)
{
     if( (a.height - b.height) < 0 )
         return true;
     return false; 
}


int main()
{
    long N, H, U, sum=0;
    int i, curent;
    Gutuie elem, *g;
    //list<Gutuie> gutui;
    list<Gutuie>::iterator it,aux;
    
    FILE * in = fopen("gutui.in", "r");
    if(in==NULL)
		return -1;	

	fscanf(in, "%ld", &N);
	fscanf(in, "%ld", &H);
	fscanf(in, "%ld", &U);
//	cout<<N<<" "<<H<<" "<<U<<endl; 
	g=(Gutuie *)malloc(N*sizeof(Gutuie));
	for(i=0; i<N; i++)
	{
		fscanf(in, "%ld", &g[i].height);
        fscanf(in, "%ld", &g[i].weight);
        g[i].level=(H-g[i].height)/U + 1;
//        gutui.push_front(elem);
//        cout << "h:" << elem.height << " w:" << elem.weight;
//        cout << endl;
	}
	fclose(in);
	qsort (g, N, sizeof(Gutuie), compare);
//	for(i=0; i<N; i++)
//        cout <<g[i].height <<" "<<g[i].weight<<" "<<g[i].level<<endl;
//	cout << endl;
//	gutui.sort(compareH);
//	for (it=gutui.begin(); it!=gutui.end(); ++it)
//		it->level=(H-it->height)/U + 1;

    list<Gutuie> gutui (g, g+N);
//    cout<<"size: "<<(int)gutui.size()<<endl;
//    for (it=gutui.begin(); it!=gutui.end(); ++it)
//         cout << "h:" << it->height << " w:" << it->weight<<endl;
    cout << endl;
	while(!gutui.empty())
	{
         it=gutui.begin();
         curent=it->level;
         if(curent==0)
             break;
         aux=it;
         while(curent==it->level)
         {
             it->level--;
             if(aux->weight < it->weight)
             {
                  aux=it;                     
             }
             ++it;
         }
         sum+=aux->weight;
         aux=gutui.erase(aux);
    }
    FILE * out = fopen("gutui.out", "w");
    fprintf(out,"%ld", sum);
    fclose(out);	
//    int x;
//    cin>>x;
    return 0;    
}