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

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

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

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

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

1. 离开手术室

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

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

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

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

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

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

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

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

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

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

AC代码1

#include<stdio.h>
#include<vector>
#include<queue>
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<Patient> v;

struct Room {
  int useTime;
  bool use;
  int endTime;
};
vector<Room> opV;
vector<Room> 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<PrioItem> 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 Room\n");
  printf(" #  Name     Room#  Begin   End      Bed#  Begin    End\n");
  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 Utilization\n");
  printf("Type  # Minutes  %% Used\n");
  printf("-------------------------\n");
  int i;
  for(i = 0; i < opV.size(); ++i) {
    printf("Room %2d %7d %7.2lf\n",i+1, opV[i].useTime, outUsed(i, 0));
  }
  for(i = 0; i < reV.size(); ++i) {
    printf("Bed  %2d %7d %7.2lf\n",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<PrioItem>();
  
  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<stdio.h>
#include<vector>
#include<queue>
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<Patient> v;

struct Room {
  int useTime;
  bool use;
};
vector<Room> opV;
vector<Room> 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;
    /*
    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<PrioItem, vector<PrioItem>, greater<PrioItem>> 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 Room\n");
  printf(" #  Name     Room#  Begin   End      Bed#  Begin    End\n");
  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 Utilization\n");
  printf("Type  # Minutes  %% Used\n");
  printf("-------------------------\n");
  int i;
  for(i = 0; i < opV.size(); ++i) {
    printf("Room %2d %7d %7.2lf\n",i+1, opV[i].useTime, outUsed(i, 0));
  }
  for(i = 0; i < reV.size(); ++i) {
    printf("Bed  %2d %7d %7.2lf\n",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<PrioItem, vector<PrioItem>, greater<PrioItem>>();
  
  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;
}