Cod sursa(job #437815)
Utilizator | Tanase Cristina cristinam.tanase | Data | 10 aprilie 2010 02:49:02 |
---|---|---|---|
Problema | Gutui | Scor | 0 |
Compilator | cpp | Status | done |
Runda | teme_upb | Marime | 3.33 kb |
#include<stdio.h>
// #include<conio.h>
struct gutu {
int h; //inaltime
int g; //greutate
int p; //prioritate
};
gutu gutui[10000];
int oc[10000];
void quickSortG(gutu vect[], int stanga, int dreapta) {
int i = stanga, j = dreapta;
gutu tmp;
int pivot = vect[(stanga + dreapta) / 2].g;
while (i <= j) {
while (vect[i].g > pivot)
i++;
while (vect[j].g < pivot)
j--;
if (i <= j) {
tmp = vect[i];
vect[i] =vect[j];
vect[j] = tmp;
i++;
j--;
}
};
if (stanga < j)
quickSortG(vect, stanga, j);
if (i < dreapta)
quickSortG(vect, i, dreapta);
}
void quickSorth(gutu vect[], int stanga, int dreapta) {
int i = stanga, j = dreapta;
gutu tmp;
int pivot = vect[(stanga + dreapta) / 2].h;
while (i <= j) {
while (vect[i].h < pivot)
i++;
while (vect[j].h > pivot)
j--;
if (i <= j) {
tmp = vect[i];
vect[i] =vect[j];
vect[j] = tmp;
i++;
j--;
}
};
if (stanga < j)
quickSorth(vect, stanga, j);
if (i < dreapta)
quickSorth(vect, i, dreapta);
}
int main(){
FILE *f,*g;
int N, H, U, i, auxh,pondere[100],max=0,iaics[100],k,s,stanga;
f = fopen( "gutui.in", "r" );
g = fopen( "gutui.out", "w" );
fscanf(f, "%d", &N);
fscanf(f, "%d", &H);
fscanf(f, "%d", &U);
for( i = 0; i < N; i ++){
fscanf ( f, "%d", &auxh );
gutui[i].h=(H-auxh)/U+1;
if(gutui[i].h > max)
max=gutui[i].h;
fscanf ( f, "%d", &gutui[i].g );
}
quickSortG(gutui,0,N-1);
int ind,j;
int cules=1;
i=0;
int ok=1;
while(i<N && ok==1){
if(oc[gutui[i].h]==0){
oc[gutui[i].h]=1;
gutui[i].p=gutui[i].h ;
s=s+gutui[i].g;
}
else { ind=gutui[i].h;
while(oc[ind]!=0 && ind>0 )
ind--;
if(ind>0){
oc[ind]=1;
gutui[i].p=ind;
s=s+gutui[i].g;}
else
ok=0;}
i++;
}
fprintf(g,"%d",s);
// getch();
return 0;
}