Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 2 KB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define URES (~0)
typedef struct {
size_t index;
size_t hatarido;
size_t buntetes;
} ugy_t;
int ugy_cmp(const void *a, const void *b)
{
const ugy_t *u1 = a, *u2 = b;
if (u1->buntetes == u2->buntetes) {
if (u1->hatarido > u2->hatarido)
return 1;
else if (u1->hatarido < u2->hatarido)
return -1;
return 0;
}
if (u1->buntetes > u2->buntetes)
return -1;
return 1;
}
size_t helyet_keres(size_t *nap, size_t ugyek, size_t i)
{
size_t orig = i;
if (nap[i] == URES)
return i;
if (i)
do {
i--;
if (nap[i] == URES)
return i;
} while (i != 0);
for (i = ugyek - 1; i > orig; i--)
if (nap[i] == URES)
return i;
printf("ohooo, bali valamit elrontott\n");
return 0;
}
size_t buntetes(ugy_t *ugy, size_t *nap, size_t ugyek)
{
size_t b = 0, hely, i;
qsort(ugy, ugyek, sizeof(ugy_t), ugy_cmp);
for (i = 0; i < ugyek; i++)
nap[i] = URES;
for (i = 0; i < ugyek; i++) {
hely = helyet_keres(nap, ugyek, ugy[i].hatarido);
nap[hely] = i;
if (hely > ugy[i].hatarido)
b += ugy[i].buntetes;
}
return b;
}
int main(int argc, char **argv)
{
ugy_t *ugy;
size_t *nap, ugyek, i;
if (scanf("%u", &ugyek) != 1) {
fprintf(stderr, "Hibas bemenet: ugyek szama hianyzik\n");
return 1;
}
ugy = malloc(ugyek * sizeof(ugy_t));
if (!ugy) {
fprintf(stderr, "Nem tudok %u bajt memoriat foglalni\n", ugyek * sizeof(ugy_t));
return 1;
}
nap = malloc(ugyek * sizeof(size_t));
if (!nap) {
fprintf(stderr, "Nem tudok %u bajt memoriat foglalni\n", ugyek * sizeof(size_t));
free(nap);
return 1;
}
for (i = 0; i < ugyek; i++) {
if (scanf("%u %u\n", &ugy[i].hatarido, &ugy[i].buntetes) != 2) {
fprintf(stderr, "Hibas bemenenet: problemas ugy\n");
free(nap);
free(ugy);
return 1;
}
ugy[i].hatarido--;
ugy[i].index = i;
}
printf("%u\n", buntetes(ugy, nap, ugyek));
for (i = 0; i < ugyek; i++)
printf("%u\n", ugy[nap[i]].index + 1);
free(nap);
free(ugy);
return 0;
}
