The question link is as follows:
Online Judge
Simulation questions. I always feel that there is not much point in doing this kind of questions, because I am digging into various format details, which is very annoying. Because there was a place where there should be two spaces, I typed three spaces, presentation error, and searched for a full hour and a half… (I have a bit of obsessive-compulsive disorder…) I finally got AC.
There are many pitfalls in this question, and I only found out about it after reading other people’s blogs. for example:
There are multiple sets of data, and each set of data is output with a blank line, including the last set of arrays;
There is a blank line between the two tables; the first table has a space before each row but the second table does not;
If the surgeries of two patients are completed at the same time, select the bed according to the operating room ID (I can’t tell this);
You need to choose a bed immediately after the surgery, and the bed needs to be available at this time.
code show as below:
#include <cstdio>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <set>
#include <algorithm>
// #define debug
std::vector<int> e1, availableR, assignR;
int n, m, start, trans, pre1, pre2, pnbr, t1, t2, t, pi, last;
char ch[9];
struct cmp1{
bool operator()(int & amp;a, int & amp;b){
return availableR[a] != availableR[b] ? availableR[a] > availableR[b] : a > b;
}
};
struct cmp2{
bool operator()(int & amp;a, int & amp;b){
return e1[a] != e1[b] ? e1[a] > e1[b] : assignR[a] > assignR[b];
}
};
int main(){
#ifdef debug
freopen("0.txt", "r", stdin);
freopen("1.txt", "w", stdout);
#endif
while (scanf("%d %d %d %d %d %d %d", & amp;n, & amp;m, & amp;start, & amp;trans, & amp;pre1, & amp ;pre2, & amp;pnbr) == 7){
std::vector<int> surg, recv, s1, s2, e2, availableB, accuR, accuB, assignB;
std::vector<std::string> patient;
std::set<int> st;
std::priority_queue<int, std::vector<int>, cmp1> roomQ;
std::priority_queue<int, std::vector<int>, cmp2> q;
for (int i = 0; i < pnbr; + + i){
scanf("%s %d %d", ch, & amp;t1, & amp;t2);
patient.push_back(ch);
surg.push_back(t1);
recv.push_back(t2);
}
availableR.resize(n + 1);
availableB.resize(m + 1);
accuR.resize(n + 1, 0);
accuB.resize(m + 1, 0);
start *= 60;
for (int i = 1; i <= n; + + i){
availableR[i] = start;
roomQ.push(i);
}
for (int i = 1; i <= m; + + i){
availableB[i] = start;
}
s1.resize(pnbr);
e1.resize(pnbr);
s2.resize(pnbr);
e2.resize(pnbr);
assignR.resize(pnbr);
assignB.resize(pnbr);
st.insert(start);
t = start;
pi = 0;
last = t;
while (1){
if (!st.count(t)){
t + + ;
continue;
}
for (; pi < pnbr; + + pi){
if (!roomQ.empty() & amp; & amp; availableR[roomQ.top()] <= t){
int temp = roomQ.top();
assignR[pi] = temp;
s1[pi] = t;
e1[pi] = t + surg[pi];
s2[pi] = e1[pi] + trans;
e2[pi] = s2[pi] + recv[pi];
last = std::max(last, e2[pi]);
st.insert(e1[pi]);
st.insert(e1[pi] + pre1);
roomQ.pop();
accuR[temp] + = surg[pi];
availableR[temp] = t + surg[pi] + pre1;
roomQ.push(temp);
q.push(pi);
} else {
break;
}
}
while (1){
if (q.empty() || e1[q.top()] > t){
break;
}
int p = q.top();
q.pop();
for (int i = 1; i <= m; + + i){
if (availableB[i] <= t){
assignB[p] = i;
accuB[i] + = recv[p];
availableB[i] = t + trans + recv[p] + pre2;
st.insert(availableB[i]);
break;
}
}
}
t + + ;
if (pi == pnbr & amp; & amp; q.empty()){
break;
}
}
printf("Patient Operating Room Recovery Room\\
");
printf(" # Name Room# Begin End Bed# Begin End\\
");
printf("--------------------------------------------- --------\\
");
for (int i = 0; i < pnbr; + + i){
printf("- %-8s - -: d -: d - -: d -: d\\
", i + 1, patient[i].c_str(), assignR[i],
s1[i] / 60, s1[i] % 60, e1[i] / 60, e1[i] % 60, assignB[i], s2[i] / 60, s2[i] % 60, e2[i ] / 60, e2[i] % 60);
}
int tot = last - start;
if (tot == 0){
tot = 1;
}
printf("\\
");
printf("Facility Utilization\\
");
printf("Type # Minutes % Used\\
");
printf("-------------------------\\
");
for (int i = 1; i <= n; + + i){
printf("Room -? %5.2f\\
", i, accuR[i], accuR[i] * 100.0 / tot);
}
for (int i = 1; i <= m; + + i){
printf("Bed -? %5.2f\\
", i, accuB[i], accuB[i] * 100.0 / tot);
}
printf("\\
");
availableR.clear();
e1.clear();
assignR.clear();
}
#ifdef debug
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
I woke up in the middle of the night and couldn’t sleep. I thought about this question and came up with some ideas for improvement… This question doesn’t need to be as troublesome as traversing it every minute. The modified code this morning is as follows:
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
// #define debug
std::vector<int> e1, availableR, assignR;
int n, m, start, trans, pre1, pre2, pnbr, t1, t2, last;
char ch[9];
struct cmp1{
bool operator()(int & amp;a, int & amp;b){
return availableR[a] != availableR[b] ? availableR[a] > availableR[b] : a > b;
}
};
bool cmp2(const int & amp;a, const int & amp;b){
return e1[a] != e1[b] ? e1[a] < e1[b] : assignR[a] < assignR[b];
}
int main(){
#ifdef debug
freopen("0.txt", "r", stdin);
freopen("1.txt", "w", stdout);
#endif
while (scanf("%d %d %d %d %d %d %d", & amp;n, & amp;m, & amp;start, & amp;trans, & amp;pre1, & amp ;pre2, & amp;pnbr) == 7){
std::vector<int> surg, recv, s1, s2, e2, availableB, accuR, accuB, assignB, pVec;
std::vector<std::string> patient;
std::priority_queue<int, std::vector<int>, cmp1> roomQ;
for (int i = 0; i < pnbr; + + i){
scanf("%s %d %d", ch, & amp;t1, & amp;t2);
patient.push_back(ch);
surg.push_back(t1);
recv.push_back(t2);
pVec.push_back(i);
}
availableR.resize(n + 1);
availableB.resize(m + 1);
accuR.resize(n + 1, 0);
accuB.resize(m + 1, 0);
start *= 60;
for (int i = 1; i <= n; + + i){
availableR[i] = start;
roomQ.push(i);
}
for (int i = 1; i <= m; + + i){
availableB[i] = start;
}
s1.resize(pnbr);
e1.resize(pnbr);
s2.resize(pnbr);
e2.resize(pnbr);
assignR.resize(pnbr);
assignB.resize(pnbr);
last = start;
for (int i = 0; i < pnbr; + + i){
int temp = roomQ.top();
assignR[i] = temp;
s1[i] = availableR[temp];
e1[i] = s1[i] + surg[i];
s2[i] = e1[i] + trans;
e2[i] = s2[i] + recv[i];
last = std::max(last, e2[i]);
roomQ.pop();
availableR[temp] = e1[i] + pre1;
roomQ.push(temp);
accuR[temp] + = surg[i];
}
sort(pVec.begin(), pVec.end(), cmp2);
for (int i = 0; i < pVec.size(); + + i){
for (int j = 1; j <= m; + + j){
if (availableB[j] <= e1[pVec[i]]){
assignB[pVec[i]] = j;
availableB[j] = e2[pVec[i]] + pre2;
accuB[j] + = recv[pVec[i]];
break;
}
}
}
printf("Patient Operating Room Recovery Room\\
");
printf(" # Name Room# Begin End Bed# Begin End\\
");
printf("--------------------------------------------- --------\\
");
for (int i = 0; i < pnbr; + + i){
printf("- %-8s - -: d -: d - -: d -: d\\
", i + 1, patient[i].c_str(), assignR[i],
s1[i] / 60, s1[i] % 60, e1[i] / 60, e1[i] % 60, assignB[i], s2[i] / 60, s2[i] % 60, e2[i ] / 60, e2[i] % 60);
}
int tot = last - start;
if (tot == 0){
tot = 1;
}
printf("\\
");
printf("Facility Utilization\\
");
printf("Type # Minutes % Used\\
");
printf("-------------------------\\
");
for (int i = 1; i <= n; + + i){
printf("Room -? %5.2f\\
", i, accuR[i], accuR[i] * 100.0 / tot);
}
for (int i = 1; i <= m; + + i){
printf("Bed -? %5.2f\\
", i, accuB[i], accuB[i] * 100.0 / tot);
}
printf("\\
");
availableR.clear();
e1.clear();
assignR.clear();
}
#ifdef debug
fclose(stdin);
fclose(stdout);
#endif
return 0;
}