当前位置: 代码迷 >> 综合 >> PAT1026 Table Tennis (30)(排队模拟)
  详细解决方案

PAT1026 Table Tennis (30)(排队模拟)

热度:13   发布时间:2024-01-16 13:23:43.0
又是排队模拟,PAT很喜欢出排队模拟题,这题巨复杂,反正我是没想出来,基本的思路就是分为桌子为VIP和选手为VIP一共4种情况讨论,太复杂。抄了一下别人的代码,其中的几个难点写了注释。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define INF 0xfffffff
using namespace std;struct person {int arrive, start, time;bool vip;
}tempPerson;struct tableNode {int end = 8 * 3600, num;bool vip;
};vector<person> player;
vector<tableNode> table;void alloctable(int personID, int tableID) {if (player[personID].arrive <= table[tableID].end)	//选手到达时前面还有人在占用桌子player[personID].start = table[tableID].end;elseplayer[personID].start = player[personID].arrive;table[tableID].end = player[personID].start + player[personID].time;table[tableID].num++;
}int findNextVip(int vipID) {vipID++;while (vipID < player.size() && player[vipID].vip == false) vipID++;return vipID;
}int main() {int n, m, k, vipTable;cin >> n;for (int i = 0; i < n; i++) {int h, m, s, tempTime, flag;scanf("%d:%d:%d %d %d", &h, &m, &s, &tempTime, &flag);tempPerson.arrive = h * 3600 + m * 60 + s;tempPerson.start = 21 * 3600;				//这里需要加,为了配合后面table[index].end>= 21 * 3600脱出if (tempPerson.arrive >= 21 * 3600) continue;//也就是说此时无法在9点前占台,最后将不会打印。tempPerson.time = tempTime<=120?tempTime*60:7200;tempPerson.vip = ((flag == 1 ? true : false));player.push_back(tempPerson);}scanf("%d%d", &m, &k);table.resize(m + 1);for (int i = 0; i < k; i++) {cin >> vipTable;table[vipTable].vip = true;}sort(player.begin(), player.end(), [](const person &a, const person &b) {return a.arrive < b.arrive;});int i = 0, vipID = -1;					vipID = findNextVip(vipID);						//指向第一个VIP选手while (i < player.size()) {int index = -1, minEndTime = INF;for (int j = 1; j <= m; j++) {if (table[j].end < minEndTime) {minEndTime = table[j].end;index = j;}}if (table[index].end >= 21 * 3600)			//已经超过营业时间break;if (player[i].vip == true && i < vipID) {	//有VIP选手插队时,该处情况就是第i个选手是已经i++;										//插队进入的VIP选手,所以直接跳过continue;}if (table[index].vip == true) {				//桌子是VIP桌if (player[i].vip == true) {				//当前选手是VIPalloctable(i, index);if (i == vipID)						//当前VIP选手占台,所以不再是第一个VIPvipID = findNextVip(vipID);i++;}else {if (vipID < player.size() && player[vipID].arrive <= table[index].end) {alloctable(vipID, index);		//此时队列中第一个VIP选手已经在等待vipID = findNextVip(vipID);		//选取该VIP选手占台//i++;							//此时当前的选手被VIP选手插队,所以不能i++				}else {								//不然该选手就失去占台机会alloctable(i, index);i++;}}}else {if (player[i].vip == false) {alloctable(i, index);i++;}else {									//桌子不为VIP桌而选手为VIP选手int vipIndex = -1, minVipEndTime = INF;for (int j = 1; j <= m; j++) {if (table[j].vip == true && minVipEndTime > table[j].end) {minVipEndTime = table[j].end;vipIndex = j;}}if (vipIndex != -1 && table[vipIndex].end <= player[i].arrive) {alloctable(i, vipIndex);			//对于当前VIP选手有其他VIP台空出来,进入VIP台if (i == vipID)				vipID = findNextVip(vipID);i++;}else {	alloctable(i, index);			//对于当前VIP选手有没有其他VIP台空出来,进入普通台if (i == vipID)vipID = findNextVip(vipID);i++;}}}}sort(player.begin(), player.end(), [](const person &a, const person &b) {return a.start < b.start;});for (int i = 0; i < player.size() && player[i].start < 21 * 3600; i++) {printf("%02d:%02d:%02d ", player[i].arrive / 3600, player[i].arrive % 3600 / 60, player[i].arrive % 60);printf("%02d:%02d:%02d ", player[i].start / 3600, player[i].start % 3600 / 60, player[i].start % 60);printf("%.0f\n", round((double)((player[i].start - player[i].arrive) / 60.0)));}for (int i = 1; i <= m; i++) {if (i != 1)printf(" ");printf("%d", table[i].num);}return 0;
}

  相关解决方案