Cod sursa(job #1873362)

Utilizator contnouAndrei Pavel contnou Data 8 februarie 2017 23:17:09
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <fstream>
#include <queue>
#include <vector>
#include <functional>

#define MAXPROCESSORS 100005
using namespace std;

ifstream f("fabrica.in");
ofstream g("fabrica.out");

struct HeapItem {
	int time;
	int execDuration;

	HeapItem() {
		time = execDuration = 0;
	}

	HeapItem(int gTime, int gExecDuration) {
		time = gTime;
		execDuration = gExecDuration;
	}

	bool operator <(const HeapItem &i) const {
		if (i.time == time) return i.execDuration < execDuration;
		return i.time < time;
	}

};

void readData(int *procA, int *procB, int &procACount, int &procBCount, int &cansCount) {
	//
	f >> cansCount >> procACount >> procBCount;

	for (int i = 0; i < procACount; i++) {
		f >> procA[i];
	}

	for (int i = 0; i < procBCount; i++) {
		f >> procB[i];
	}
}

int getMax(int m1, int m2) {
	//
	return m1 > m2 ? m1 : m2;
}

void computeFinishingTimeForProcessors(int *processors, int processorsCount, int cansCount, int *finishingTimes, int &procMinTime) {
	//
	priority_queue<HeapItem> processorsHeap;

	for (int i = 0; i < processorsCount; i++) {
		processorsHeap.push(HeapItem(processors[i], processors[i]));
	}

	procMinTime = 0;
	for (int i = 0; i < cansCount; i++) {
		//
		HeapItem first = processorsHeap.top();
		processorsHeap.pop();

		finishingTimes[i] = first.time;
		procMinTime = getMax(procMinTime, finishingTimes[i]);

		first.time += first.execDuration;
		processorsHeap.push(first);

	}
}

void computeMinimumTimes(int *procA, int procACount, int *procB, int procBCount, int cansCount, int &procAMinTime, int &finalPhaseTime) {
	//
	priority_queue<HeapItem> procAHeap, procBHeap;
	int finishingTimesA[MAXPROCESSORS], finishingTimesB[MAXPROCESSORS];
	int procBMinTime = 0;

	procAMinTime = 0;

	computeFinishingTimeForProcessors(procA, procACount, cansCount, finishingTimesA, procAMinTime);
	computeFinishingTimeForProcessors(procB, procBCount, cansCount, finishingTimesB, procBMinTime);
	
	finalPhaseTime = 0;
	for (int i = 0; i < cansCount; i++) {
		//
		finalPhaseTime = getMax(finalPhaseTime, finishingTimesA[i] + finishingTimesB[cansCount - 1 - i]);
	}
}

int main() {
	//
	int procA[MAXPROCESSORS], procB[MAXPROCESSORS];
	int procACount, procBCount, cansCount;
	int procAMinTime, procBMinTime;

	readData(procA, procB, procACount, procBCount, cansCount);
	computeMinimumTimes(procA, procACount, procB, procBCount, cansCount, procAMinTime, procBMinTime);

	g << procAMinTime << " " << procBMinTime;
	return 0;
}