[刷题]算法竞赛入门经典(第2版) 5-16/UVa212 - Use of Hospital Facilities

题意：模拟患者做手术。

其条件为：医院有Nop个手术室、准备手术室要Mop分钟，另有Nre个恢复用的床、准备每张床要Mre分钟，早上Ts点整医院开张，从手术室手术完毕转移到回复床要Mtr分钟。现在医院早上开张了，给你一张患者的表，有Npa个患者等着做手术，每个患者的的信息有：名字、做手术需要的时间、恢复需要的时间。只要有空的手术室位就安排患者进去，优先安排门牌号低的。若多人同时竞争，输入列表靠前的先进。进入恢复室的优先顺序是，也是优先安排床号靠前的床，同时做完手术的人按照手术室的门牌号小的 （很奇葩的设定）优先。

代码：（Accepted，0.000s）

//UVa212 - Use of Hospital Facilities

//Accepted 0.000s

//#define _XIENAOBAN_

#include<algorithm>

#include<iostream>

#include<iomanip>

#include<utility>

#include<string>

#include<vector>

#include<queue>

#define ipt cin

#define opt cout//just for convenience and appearance, because size("cout"+" ")=5, which is longer than a tab(which is 4)

#define time_convert(t) setw(2) << (t / 60) << ':' << setfill('0') << setw(2) << (t % 60) << setfill(' ')

using namespace std;

struct ROOM {

    int id, at;

    ROOM() {}

    ROOM(int a, int b) :id(a), at(b) {}

    bool operator <(const ROOM& that) const {

        if (at != that.at) return at > that.at;

        return id > that.id;

    }

};

struct PATIENT {

    string name;

    int id, room, bed, top, tre, t1, t2, t3, t4;

};

int Nop, Nre, Ts, Te, Mtr, Mop, Mre, Npa;

int main()

{

#ifdef _XIENAOBAN_

#define gets(T) gets_s(T, 66666)

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    ios::sync_with_stdio(false);

    while (ipt >> Nop) {

        ipt >> Nre >> Ts >> Mtr >> Mop >> Mre >> Npa;

        Te = 0, Ts *= 60;

        vector<int> Top(Nop + 1, 0), Tre(Nre + 1, 0);

        vector<PATIENT> Info(Npa + 1);

        vector<int> Bre(Nre + 1, Ts);

        priority_queue<ROOM> Rop;

        for (int i(1);i <= Nop;++i) Rop.push(ROOM(i, Ts));

        //For all the operating rooms

        for (int N(1);N <= Npa;++N) {

            auto& now(Info[N]);

            now.id = N;

            ROOM op(Rop.top());

            Rop.pop();

            ipt >> now.name >> now.top >> now.tre;

            now.t1 = op.at;

            now.t2 = now.t1 + now.top;

            now.t3 = now.t2 + Mtr;

            now.t4 = now.t3 + now.tre;

            now.room = op.id;

            op.at = now.t2 + Mop;

            Top[op.id] += now.top;

            Rop.push(op);

        }

        sort(Info.begin() + 1, Info.end(), [](PATIENT& a, PATIENT& b)->bool

        {if (a.t2 != b.t2) return a.t2 < b.t2;return a.room < b.room;});//Sort by t2

        //For all the recovery rooms

        for (int N(1);N <= Npa;++N) {

            auto& now(Info[N]);

            int re;

            for (re = 1;re <= Nre;++re)

                if (Bre[re] <= now.t2) break;

            now.bed = re;

            Bre[re] = now.t4 + Mre;

            Tre[re] += now.tre;

            if (Te < now.t4) Te = now.t4;

        }

        sort(Info.begin() + 1, Info.end(), [](PATIENT& a, PATIENT& b) {return a.id < b.id;});//Sort by id

        //Output

        opt << " Patient          Operating Room          Recovery Room\n"

            << " #  Name     Room#  Begin   End      Bed#  Begin    End\n"

            << " ------------------------------------------------------\n";

        for (int N(1);N <= Npa;++N) {

            auto& now(Info[N]);

            opt << setw(2) << N << "  " << left << setw(10) << now.name << right << setw(2)

                << now.room << "   " << time_convert(now.t1) << "   " << time_convert(now.t2) << "     " << setw(2)

                << now.bed << "   " << time_convert(now.t3) << "   " << time_convert(now.t4) << '\n';

        }

        opt << '\n'

            << "Facility Utilization\n"

            << "Type  # Minutes  % Used\n"

            << "-------------------------\n";

        for (int N(1);N <= Nop;++N) {

            opt << "Room " << setw(2) << N << setw(8) << Top[N]

                << setw(8) << fixed << setprecision(2) << (Top[N] * 100.0 / (float)(Te - Ts)) << '\n';

        }

        for (int N(1);N <= Nre;++N) {

            opt << "Bed  " << setw(2) << N << setw(8) << Tre[N]

                << setw(8) << fixed << setprecision(2) << (Tre[N] * 100.0 / (float)(Te - Ts)) << '\n';

        }

        cout << endl;

    }

    return 0;

}

分析：终于是本章节的最后一题啦！书上说很难，感觉其实不难啊，就是麻烦了点，写了好久。就是死在了一句话上“If two patients emerge from surgery at the same time, the patient with the lower number will be the first assigned to a recovery room bed.”（就是上面题意里加黑的那句）我还以为指的是患者编号，即患者输入顺序。结果WA。。。udebug上没有数据，不知道问题在哪里。自己做了一套数据发现了错误，百度查了别人的排序逻辑，才发现原来那个the patient with the lower number指的是在门牌号小的手术室做手术的患者。那个number竟然指的门牌号！所以只把sort函数的lambda比较函数改了一小下就AC了。

手术室的模拟使用了优先队列，空一个房间就来一个人，但是恢复床位不能用优先队列。因为恢复床位进入可使用状态最早的不一定是床号最小的，即当有人要转移到床位时可使用床位可能不止一个，和他做完手术的时间有关系。

附：测试数据

10 30 01 16 15 1 30 Jones 90 140 Smith 10 200 Thompson 60 75 Albright 40 82 Poucher 33 209 Comer 10 201 Perry 3 188 Page 111 120 Roggio 69 100 Brigham 42 79 Nute 22 71 Young 38 50 Bush 26 40 Cates 120 32 Johnson 10 2 Jones 28 140 Smith 120 200 Thompson 23 75 Albright 19 82 Poucher 133 209 Comer 74 101 Perry 93 188 Page 111 223 Roggio 69 122 Brigham 42 79 Nute 22 71 Young 38 140 Bush 26 121 Cates 120 248 Johnson 10 50