Programozás‎ > ‎Feladatok‎ > ‎Pályázatok‎ > ‎Megoldás‎ > ‎

ve_palyazat.cpp

Letöltés: ve_palyazat.cpp

#include <iostream>
#include <stdio.h>
 
#define max(a, b) (a>b?a:b)
 
using namespace std;
 
struct munka {
    unsigned int haszon, sorszam, hatarido;
};
 
struct lista {
    unsigned int elem;
    lista *kov;
    lista(unsigned int e) {
        elem = e;
        kov = NULL;
    }
};
 
munka munkak[10000];
unsigned int munkakL;
 
void listaRendez(lista **l) {
    lista *ujLista = NULL, *nezettelem = NULL, *elozoelem = NULL, *kov = NULL;
    while(*l != NULL) {
        kov = (*l)->kov;
        if (ujLista == NULL) {
            ujLista = *l;
            ujLista->kov = NULL;
        } else {
            nezettelem = ujLista;
            elozoelem = NULL;
            while(true) {
                if (munkak[nezettelem->elem].hatarido > munkak[(*l)->elem].hatarido) {
                    (*l)->kov = nezettelem;
                    if (elozoelem != NULL) elozoelem->kov = *l;
                    else ujLista = *l;
                    break;
                }
                elozoelem = nezettelem;
                nezettelem = nezettelem->kov;
                if (nezettelem == NULL) {
                    (*l)->kov = NULL;
                    elozoelem->kov = *l;
                    break;
                }
            }
        }
        *l = kov;
    }
    *l = ujLista;
}
 
bool lehet(lista *hely) {
    unsigned int i, maxNap = 0, munkakSzama;
    lista *nezetthely = hely;
    while (nezetthely != NULL) {
        maxNap = max(maxNap, munkak[nezetthely->elem].hatarido);
        nezetthely = nezetthely->kov;
    }
    for (i = maxNap-1; ; i--) {
        munkakSzama = 0;
        nezetthely = hely;
        while (nezetthely != NULL) {
            if (munkak[nezetthely->elem].hatarido <= i+1) munkakSzama++;
            if (munkakSzama>i+1) return false;
            nezetthely = nezetthely->kov;
        }
        if (i == 0) return true;
    }
    return true;
}
 
int main(int argc, char **argv) {
    unsigned int i, j;
    FILE *file = fopen(argv[1], "r");
    fscanf(file, "%i", &munkakL);
    for (i = 0; i < munkakL; i++) {
        fscanf(file, "%i %i", &(munkak[i].hatarido), &(munkak[i].haszon));
        munkak[i].sorszam = i+1;
    }
    fclose(file);
    munka tMunka;
    for (i = 0; i < munkakL-1; i++) {
        for (j = i+1; j < munkakL; j++) {
            if (munkak[i].haszon < munkak[j].haszon) {
                tMunka = munkak[i];
                munkak[i] = munkak[j];
                munkak[j] = tMunka;
            }
        }
    }
    /*for (i = 0; i < munkakL; i++) {
        printf("%i. %i-ig %i\n", munkak[i].sorszam, munkak[i].hatarido, munkak[i].haszon);
    }*/
    lista *jomunkak = NULL, *utolsoElem = NULL;
    long osszHaszon = 0;
    for (i = 0; i < munkakL; i++) {
        if (utolsoElem == NULL)
            jomunkak = new lista(i);
        else
            utolsoElem->kov = new lista(i);
        if (lehet(jomunkak)) {
            osszHaszon += munkak[i].haszon;
            if (utolsoElem == NULL)
                utolsoElem = jomunkak;
            else
                utolsoElem = utolsoElem->kov;
        } else {
            if (utolsoElem == NULL) {
                delete jomunkak;
                jomunkak = NULL;
            } else {
                delete utolsoElem->kov;
                utolsoElem->kov = NULL;
            }
        }
    }
    printf("%li\n", osszHaszon);
    listaRendez(&jomunkak);
    utolsoElem = jomunkak;
    while(utolsoElem != NULL) {
        printf("%i ", munkak[utolsoElem->elem].sorszam);
        utolsoElem = utolsoElem->kov;
    }
    printf("\n");
    return 0;
}