UVA-212 医院设备利用 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

这也是一道根据根据时间做出行为的题目，我的做法和之前的UVA822类似，也是用优先队列实现。

参考：

UVA-822 客户中心模拟 题解答案代码 算法竞赛入门经典第二版_漂流瓶jz的博客-CSDN博客

这道题我一开始定义了很多种事件类型，并根据不同的行为做判断（可见AC代码2）

方法本身可行，但是根本没必要。经过简化后的AC代码1，实际上只需要两种类型的事件即可：

1. 离开手术室

2. 手术室准备好，可以进入新病人。

剩下的事件比如转运病人，进入离开恢复室，准备恢复室等等事件都可以在前两个事件发生时推算出来。

尤其是选择恢复室这个关键行为，是需要在手术结束的时候就选择的，不能等到转运病人完成后再选择。这个逻辑也很好理解：如果没确定恢复室，那么就不知道往何处转运。

这选择恢复室的时候，我们就会碰到一个题目的BUG：

我们是选择当前空闲的恢复室，还是选择转运结束时才空闲的恢复室？

其实我们只需要保证转运结束时，有恢复室空闲即可，没必要必须保证手术结束的当时是空闲的。但是题目选择的行为是：选择手术结束时就已经空闲的恢复室。在题目的样例中即是如此：

 已知恢复室的准备时间为10分钟。

8:43时3号病人在2号恢复室结束恢复。8:53时2号恢复室已经准备完成，可以使用。

但是8:53时，6号病人选择了4号恢复室，没有选择2号恢复室。

已知如果多个恢复室空闲时，应该优先选择恢复室号小的。因此，题目的判断应该是要求在手术结束时选择当前空闲的恢复室。我根据这个写的代码，最后也成功AC。

AC代码1

#include
#include
#include
using namespace std;

int oproomNum, reroomNum, startTime, transTime, preop, prere, patiNum; 
struct Patient {
	char name[105];
	int opTime, reTime;
	int opNum, opBeg, opEnd, reNum, reBeg, reEnd;
}; 
vector v;

struct Room {
	int useTime;
	bool use;
	int endTime;
};
vector opV;
vector reV;

// type说明
// 1 离开oproom
// -1 准备好 oproom

struct PrioItem {
	int time;
	int type;
	int pai;
	int roomi;
	bool operator< (const PrioItem &rhs) const {
		if(time != rhs.time) {
			return time > rhs.time;
		}
		if(type != rhs.type) {
			return type > rhs.type;
		}
		return roomi > rhs.roomi;
	}
};

int pai, timeNow, endTime;
priority_queue pq;
 
// 病人开始手术
void useOpNum(int pai, int roomi) {
	PrioItem pi;
	opV[roomi].use = true;
	opV[roomi].useTime += v[pai].opTime;
	opV[roomi].endTime = timeNow + v[pai].opTime + preop;
	v[pai].opNum = roomi;
	v[pai].opBeg = timeNow;
	v[pai].opEnd = timeNow + v[pai].opTime;
	pi.time = v[pai].opEnd;
	pi.type = 1;
	pi.pai = pai;
	pi.roomi = roomi;
	pq.push(pi);
}

void handleN1(PrioItem pi) {
	if(pai >= patiNum) {
		return;
	} 
	for(int i = 0; i < opV.size(); ++i) {
		if(opV[i].endTime <= timeNow) {
			useOpNum(pai++, i);
		}
	}
}

void handle1(PrioItem pi) {
	// 转运病人
	// 转运的时候就要选择恢复室
	int i, j, k;
	for(i = 0; i < reroomNum; ++i) {
		if(reV[i].endTime <= timeNow) {
			break;
		}
	}
	if(i == reroomNum) {
		//printf("怎么会出现没有恢复室的情况？n");
		return; 
	}
	reV[i].useTime += v[pi.pai].reTime;
	v[pi.pai].reNum = i;
	v[pi.pai].reBeg = timeNow + transTime;
	v[pi.pai].reEnd = v[pi.pai].reBeg + v[pi.pai].reTime;
	if(v[pi.pai].reEnd > endTime) {
		endTime = v[pi.pai].reEnd;
	}
	reV[i].endTime = v[pi.pai].reEnd + prere;
	
	// 清理手术室事件 
	PrioItem piNew2;
	piNew2.type = -1;
	piNew2.roomi = pi.roomi;
	piNew2.time = timeNow + preop;
	pq.push(piNew2);
}

void oper() {
	int i, j, k;
	timeNow = startTime;
	PrioItem pi;
	for(pai = 0; pai < oproomNum && pai < patiNum; ++pai) {
		useOpNum(pai, pai);
	}
	while(pq.size()) {
		pi = pq.top();
		pq.pop();
		timeNow = pi.time;
		switch(pi.type) {
			case -1:
				handleN1(pi);
				break;
			case 1:
				handle1(pi);
				break;
		}
	}
	if(pai != patiNum) {
		// printf("怎么会出现没有做手术的情况？n");
		return; 
	}
}

void outTime(int t) {
	int hour = t / 60;
	int min = t % 60;
	printf("%2d:%02d", hour, min); 
}

void outPatient() {
	printf(" Patient          Operating Room          Recovery Roomn");
	printf(" #  Name     Room#  Begin   End      Bed#  Begin    Endn");
	printf(" ------------------------------------------------------n");
	int i;
	for(i = 0; i < v.size(); ++i) {
		printf("%2d  %-9s %2d   ", i+1, v[i].name, v[i].opNum + 1);
		outTime(v[i].opBeg);
		printf("   ");
		outTime(v[i].opEnd);
		printf("     %2d   ", v[i].reNum + 1);
		outTime(v[i].reBeg);
		printf("   ");
		outTime(v[i].reEnd);
		printf("n");
	}
	
}

double outUsed(int i, int type) {
	if(endTime == startTime) {
		return 0.0;
	}
	if(type == 0) {
		return (double)opV[i].useTime / (endTime-startTime) * 100;
	}
	if(type == 1) {
		return (double)reV[i].useTime / (endTime-startTime) * 100;
	}
}

void outFac() {
	printf("Facility Utilizationn");
	printf("Type  # Minutes  %% Usedn");
	printf("-------------------------n");
	int i;
	for(i = 0; i < opV.size(); ++i) {
		printf("Room %2d %7d %7.2lfn",i+1, opV[i].useTime, outUsed(i, 0));
	}
	for(i = 0; i < reV.size(); ++i) {
		printf("Bed  %2d %7d %7.2lfn",i+1, reV[i].useTime, outUsed(i, 1));
	}
}

int main() {
	int i, j;
	while(scanf("%d%d%d%d%d%d%d", &oproomNum, &reroomNum, &startTime, &transTime, &preop, &prere, &patiNum) == 7) {
	v.clear();
	opV.clear();
	reV.clear();
	pq = priority_queue();
	
	startTime = startTime * 60;
	endTime = startTime;
	for(i = 0; i < oproomNum; ++i) {
		Room m;
		m.use = false;
		m.useTime = 0;
		opV.push_back(m);
	}
	for(i = 0; i < reroomNum; ++i) {
		Room m;
		m.use = false;
		m.useTime = 0;
		m.endTime = 0;
		reV.push_back(m);
	}
	
	for(i = 0; i < patiNum; ++i) {
		Patient p;
		scanf("%s", p.name);
		scanf("%d%d", &p.opTime, &p.reTime);
		v.push_back(p);
	}
	oper();
	outPatient();
	printf("n");
	outFac();
	printf("n");
}
	
	return 0;
}

AC代码2

#include
#include
#include
using namespace std;

int oproomNum, reroomNum, startTime, transTime, preop, prere, patiNum; 
struct Patient {
	char name[10];
	int opTime, reTime;
	int opNum, opBeg, opEnd, reNum, reBeg, reEnd;
}; 
vector v;

struct Room {
	int useTime;
	bool use;
};
vector opV;
vector reV;

// type说明
// 1 离开oproom
// -1 准备好 oproom, -2 准备好reroom

struct PrioItem {
	int time;
	int type;
	int pai;
	int roomi;
	bool operator< (const PrioItem &rhs) const {
		if(time != rhs.time) {
			return time < rhs.time;
		}
		if(type != rhs.type) {
			return type < rhs.type;
		}
		return roomi < rhs.roomi;
	}
	
	bool operator== (const PrioItem &rhs) const {
		if(time == rhs.time && type == rhs.type && roomi == rhs.roomi) {
			return true;
		} return false;
	}
	
	bool operator> (const PrioItem &rhs) const {
		if(*this == rhs || *this < rhs) return false;
		return true;
		
	}
};

int pai, timeNow, endTime;
priority_queue, greater> pq;

// 病人开始手术
void useOpNum(int pai, int roomi) {
	PrioItem pi;
	opV[roomi].use = true;
	opV[roomi].useTime += v[pai].opTime;
	v[pai].opNum = roomi;
	v[pai].opBeg = timeNow;
	v[pai].opEnd = timeNow + v[pai].opTime;
	pi.time = v[pai].opEnd;
	pi.type = 1;
	pi.pai = pai;
	pi.roomi = roomi;
	pq.push(pi);
}

void handleN1(PrioItem pi) {
	opV[pi.roomi].use = false;
	if(pai >= patiNum) {
		return;
	}
	useOpNum(pai, pi.roomi);
	++pai;
}

void handleN2(PrioItem pi) {
	reV[pi.roomi].use = false;
}

void handle1(PrioItem pi) {
	// 转运病人
	// 转运的时候就要选择恢复室
	int i, j, k;
	for(i = 0; i < reroomNum; ++i) {
		if(reV[i].use == false) {
			break;
		}
	}
	if(i == reroomNum) {
		// printf("怎么会出现没有恢复室的情况？n");
		return;
	}
	reV[i].use = true;
	reV[i].useTime += v[pi.pai].reTime;
	v[pi.pai].reNum = i;
	v[pi.pai].reBeg = timeNow + transTime;
	v[pi.pai].reEnd = v[pi.pai].reBeg + v[pi.pai].reTime;
	if(v[pi.pai].reEnd > endTime) {
		endTime = v[pi.pai].reEnd;
	}
	// 直接一步到位，到清理恢复室的情况
	PrioItem piNew;
	piNew.type = -2;
	piNew.roomi = i;
	piNew.pai = pi.pai;
	piNew.time = v[pi.pai].reEnd + prere;
	pq.push(piNew);
	
	// 清理手术室
	PrioItem piNew2;
	piNew2.type = -1;
	piNew2.roomi = pi.roomi;
	piNew2.time = timeNow + preop;
	pq.push(piNew2);
}

void oper() {
	int i, j, k;
	timeNow = startTime;
	PrioItem pi;
	for(pai = 0; pai < oproomNum && pai < patiNum; ++pai) {
		useOpNum(pai, pai);
	}
	while(pq.size()) {
		pi = pq.top();
		pq.pop();
		timeNow = pi.time;
		switch(pi.type) {
			case -1:
				handleN1(pi);
				break;
			case -2:
				handleN2(pi);
				break;
			case 1:
				handle1(pi);
				break;
		}
	}
	if(pai != patiNum) {
		// printf("怎么会出现没有做手术的情况？n");
		return; 
	}
}

void outTime(int t) {
	int hour = t / 60;
	int min = t % 60;
	printf("%2d:%02d", hour, min); 
}

void outPatient() {
	printf(" Patient          Operating Room          Recovery Roomn");
	printf(" #  Name     Room#  Begin   End      Bed#  Begin    Endn");
	printf(" ------------------------------------------------------n");
	int i;
	for(i = 0; i < v.size(); ++i) {
		printf("%2d  %-9s %2d   ", i+1, v[i].name, v[i].opNum + 1);
		outTime(v[i].opBeg);
		printf("   ");
		outTime(v[i].opEnd);
		printf("     %2d   ", v[i].reNum + 1);
		outTime(v[i].reBeg);
		printf("   ");
		outTime(v[i].reEnd);
		printf("n");
	}
	
}

double outUsed(int i, int type) {
	if(endTime == startTime) {
		return 0.0;
	}
	if(type == 0) {
		return (double)opV[i].useTime / (endTime-startTime) * 100;
	}
	if(type == 1) {
		return (double)reV[i].useTime / (endTime-startTime) * 100;
	}
}

void outFac() {
	printf("Facility Utilizationn");
	printf("Type  # Minutes  %% Usedn");
	printf("-------------------------n");
	int i;
	for(i = 0; i < opV.size(); ++i) {
		printf("Room %2d %7d %7.2lfn",i+1, opV[i].useTime, outUsed(i, 0));
	}
	for(i = 0; i < reV.size(); ++i) {
		printf("Bed  %2d %7d %7.2lfn",i+1, reV[i].useTime, outUsed(i, 1));
	}
}

int main() {
	int i, j;
	while(scanf("%d%d%d%d%d%d%d", &oproomNum, &reroomNum, &startTime, &transTime, &preop, &prere, &patiNum) == 7) {
	v.clear();
	opV.clear();
	reV.clear();
	pq = priority_queue, greater>();
	
	startTime = startTime * 60;
	endTime = startTime;
	for(i = 0; i < oproomNum; ++i) {
		Room m;
		m.use = false;
		m.useTime = 0;
		opV.push_back(m);
	}
	for(i = 0; i < reroomNum; ++i) {
		Room m;
		m.use = false;
		m.useTime = 0;
		reV.push_back(m);
	}
	
	for(i = 0; i < patiNum; ++i) {
		Patient p;
		scanf("%s", p.name);
		scanf("%d%d", &p.opTime, &p.reTime);
		v.push_back(p);
	}
	oper();
	outPatient();
	printf("n");
	outFac();
	printf("n");
}
	
	return 0;
}