Pagini recente » Cod sursa (job #1937693) | Cod sursa (job #1013645) | Cod sursa (job #673571) | Cod sursa (job #2885288) | Cod sursa (job #441495)
Cod sursa(job #441495)
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
using namespace std;
typedef struct gutui {
int weight;
int pasi;
} Gutui;
int compare(const void *a, const void *b) {
Gutui* ob1 = (Gutui*) a;
Gutui* ob2 = (Gutui*) b;
if (ob1->pasi != ob2->pasi) {
if (ob1->pasi < ob2->pasi) return -1;
else return 1;
}
if (ob1->pasi == ob2->pasi) {
if (ob1->weight < ob2->weight) return 1;
else return -1;
}
return 0;
}
class mycomparison
{
public:
bool operator() (const int& lhs, const int &rhs) const
{
return (lhs>rhs);
}
};
int main()
{
int N, H, U;
int i, j, greutate = 0;//j reprezinta inaltimea gutuii
FILE *f, *g;
Gutui v[100000];
priority_queue< int, vector<int>, mycomparison > culese;
f = fopen("gutui.in", "r");
g = fopen("gutui.out", "w");
fscanf(f, "%d %d %d", &N, &H, &U);
for (i=0; i<N; i++)
{
fscanf(f, "\n%d %d", &j, &v[i].weight);
v[i].pasi = (H - j)/U + 1; //construim vectorul de pasi; adica dupa cate ridicari ale copacului, nu mai putem culege gutuia curenta
}
qsort(v, N, sizeof(Gutui), compare);//sortam crescator dupa nr de pasi, si in caz de egalitate descrescator dupa greutatea gutuii
int k=0; //reprezinta cate gutui s-au cules
for (i=0; i<N; i++)
{
if (v[i].pasi - k > 0)
{
culese.push(v[i].weight);
k++;
greutate += v[i].weight;
}
else if(culese.size()>0)
{
if (v[i].weight > culese.top())
{
greutate -= culese.top();
culese.pop();
greutate += v[i].weight;
culese.push(v[i].weight);
}
}
}
fprintf(g,"%d",greutate);
fclose(f);
fclose(g);
return 0;
}