Letöltés: uj_palyazat.cpp /*
Informatika: algoritmus szakkor
Feladat: palyazatok
Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/17ora/palyazatok
Uray M. Janos, 2010. februar 9.
*/
#include <fstream>
#include <iostream>
#include <cstdlib>
using namespace std;
#define MaxN 10000
#define MaxH 10000
struct sWork {
int ID, H, P;
};
bool Read (const char *, int &, sWork *);
bool Write (const char *, int, int, const int *);
int Compare (const void *, const void *);
int main (int nArgs, char * Arg []) {
int I, J, N;
sWork Work[MaxN];
int Time[MaxH], SumP, P;
// Argumentumok szamanak ellenorzese
if (nArgs < 3)
return 1;
// Adatok beolvasasa
if (!Read(Arg[1], N, Work))
return 1;
// Rendezes haszon szerint csokkeno sorrendben
qsort(Work, N, sizeof(sWork), Compare);
// Time inicializalasa
for (int I = 0; I < MaxH; I++)
Time[I] = 0;
SumP = 0;
// A beteheto munkak betetele az adott sorrendben
// SumP szamolja az osszes haszont
for (I = 0; I < N; I++) {
// Minden munkat eloszor a hataridore tesszuk be.
// Ha ez nem sikerul, akkor megyunk vissza az idoben, es a legelso ures
// helyre berakjuk. Ha nincs ures hely, akkor nem vegezheto el a munka.
for (J = Work[I].H - 1; J >= 0; J--)
if (Time[J] == 0)
break;
if (J >= 0) {
Time[J] = Work[I].ID;
SumP += Work[I].P;
}
}
// Eredmeny mentese
if (!Write(Arg[2], SumP, MaxH, Time))
return 1;
return 0;
}
// Adatok beolvasasa allomanybol
bool Read (const char * FN, int & N, sWork * W) {
fstream F(FN, fstream::in);
if (F.fail())
return false;
F >> N;
for (int I = 0; I < N; I++) {
F >> W[I].H >> W[I].P;
W[I].ID = I + 1;
}
F.close();
return true;
}
// Eredmeny kiirasa fajlba
bool Write (const char * FN, int SumP, int N, const int * Time) {
fstream F(FN, fstream::out);
if (F.fail())
return false;
F << SumP << endl;
for (int I = 0; I < N; I++) {
if (Time[I] != 0)
F << Time[I] << " ";
}
F << endl;
F.close();
return true;
}
// Az osszehasonlito fuggveny, amelyet a qsort hasznal
int Compare (const void * A, const void * B) {
return ((sWork *)B)->P - ((sWork *)A)->P;
}
|