Pagini recente » Cod sursa (job #2149358) | Cod sursa (job #2976468) | Cod sursa (job #585031) | Cod sursa (job #1908331) | Cod sursa (job #441008)
Cod sursa(job #441008)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
unsigned int h,u;
int n;
//structura pentru retinerea datelor de intrare
typedef struct {
unsigned int height;
unsigned int weight;
int clas; //variabila care imi indica pasul maxim la care
}gutuie; //poate fi culeasa o gutuie
//functie care compara doua gutui dupa greutate
bool my_compare(const gutuie &a,const gutuie &b){
return (a.weight > b.weight);
}
int main(){
int i,j,k=0,nrgutui=0,sum=0;
int max_dif=0;
int *solutie;
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
fscanf(fin,"%d",&n);
fgetc(fin);
fscanf(fin,"%d",&h);
fgetc(fin);
fscanf(fin,"%d",&u);
//respect restrictile
if(n<1||n>100000)
return 1;
std::vector<gutuie> vect;
gutuie aux;
//citesc datele de intrare
for( i = 0; i < n; i++){
fgetc(fin);
fscanf(fin, "%d" , &aux.height);
//verific daca gutuia poate fi culeasa
if(aux.height <= h){
fgetc(fin);
fscanf(fin,"%d",&aux.weight);
aux.clas=(h-aux.height)/u+1;
if(aux.clas > max_dif) //vad cate gutui pot culege maxim
max_dif=aux.clas;
}
else { //sar peste aceasta gutuie
i--;
n--;
}
vect.push_back(aux);
}
//vector care are pe pozitia i greutatea gutui care a fost culeasa la pasul i
//initializat cu 0
solutie=(int *)calloc(max_dif+1,sizeof(int));
//sortez dupa greutate folosind std::sort
std::sort(vect.begin(),vect.end(),my_compare);
//incep sa culeg gutui cat mai grele pana am cules destule
for( i=0 ; i<n && nrgutui <= max_dif ; i++){
k=vect[i].clas;
if( solutie[k]==0 ){ //nu am mai cules gutuie la pasul k
solutie[k] = vect[i].weight;
nrgutui++;
}
else
for(j=k-1 ; j>=0 ;j--) //am cules gutuie la pasul k si incerc
if( solutie[j]==0 ){ //sa culeg gutuia curenta anterior
solutie[j] = vect[i].weight;
nrgutui++;
break;
}
}
/*
metoda pe care am abordat-o prima data
dar care era prea lenta datorita qsortului de mai jos
in teorie si ea functioneaza
while(i<n){
k=vect[i].clas;
for( g=depl ; g < k && i < n; g++)
solutie[depl++]=vect[i++].weight;
schimb=0;
qsort(solutie,depl,sizeof(int),comp);
for(g=i;vect[g].clas==k&&schimb<k;g++)
for(j=0;j<depl&&schimb<k;j++)
if(solutie[j]<vect[g].weight) {
solutie[j]=vect[g].weight;
schimb++;
break;
}
i=g;
}
*/
//calculez greutatea maxima
for(i=1; i <= max_dif; i++)
sum+=solutie[i];
fprintf(fout,"%d",sum);
return 0;
}