解題區/解題區 - UVa

UVa 212 - Use of Hospital Facilities

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

參照《算法競賽入門經典》一書

模擬醫院的手術室和恢復室(病房)，每個病人分配到一個手術室後，手術完成後會被送至恢復室，而送病人於手術室到恢復室都需要 t1 時間，而每個病人在手術室和恢復室的時間也各有不同。

當手術室和恢復室被使用完畢後，分別需要 t2, t3 的時間進行清除整潔工作，隨後才能再給下一位病人使用，保證每一位病人在過程中都能立即使用不會延誤。

編號小的病患，會先選擇可使用的場地，場地編號也會盡可能地小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
5 12 07 5 15 10 16
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
86 181
White
92 140

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 Patient          Operating Room          Recovery Room
 #  Name     Room#  Begin   End      Bed#  Begin    End
 ------------------------------------------------------
 1  Jones      1    7:00    7:28      3    7:33    9:53
 2  Smith      2    7:00    9:00      1    9:05   12:25
 3  Thompson   3    7:00    7:23      2    7:28    8:43
 4  Albright   4    7:00    7:19      1    7:24    8:46
 5  Poucher    5    7:00    9:13      5    9:18   12:47
 6  Comer      4    7:34    8:48      4    8:53   10:34
 7  Perry      3    7:38    9:11      2    9:16   12:24
 8  Page       1    7:43    9:34      6    9:39   13:22
 9  Roggio     4    9:03   10:12      9   10:17   12:19
10  Brigham    2    9:15    9:57      8   10:02   11:21
11  Nute       3    9:26    9:48      7    9:53   11:04
12  Young      5    9:28   10:06      3   10:11   12:31
13  Bush       1    9:49   10:15     10   10:20   12:21
14  Cates      3   10:03   12:03      8   12:08   16:16
15  Johnson    2   10:12   11:38      4   11:43   14:44
16  White      5   10:21   11:53      7   11:58   14:18
Facility Utilization
Type  # Minutes  % Used
-------------------------
Room  1     165   29.68
Room  2     248   44.60
Room  3     258   46.40
Room  4     162   29.14
Room  5     263   47.30
Bed   1     282   50.72
Bed   2     263   47.30
Bed   3     280   50.36
Bed   4     282   50.72
Bed   5     209   37.59
Bed   6     223   40.11
Bed   7     211   37.95
Bed   8     327   58.81
Bed   9     122   21.94
Bed  10     121   21.76
Bed  11       0    0.00
Bed  12       0    0.00

Solution

建議使用一種時間軸的概念，維護一個 priority_queue 來知道下一個事件發生時間，接著在那時間掃描可能發生事件，這樣維護會比較容易寫。

出題者到處打雜呢！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <sstream>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct Patient {
    string name;
    int pa, pb;
    int aBegin, aEnd, bBegin, bEnd, aid, bid;
    Patient(int a = 0, int b = 0, string s = ""):
    pa(a), pb(b), name(s) {}
} D[2048];
int main() {
    int N, M, K, ST_T, PA_T, PB_T, PAB_T;
    char s[1024];
    int x, y;
    while (scanf("%d %d %d %d %d %d %d", &N, &M, &ST_T, &PAB_T, &PA_T, &PB_T, &K) == 7) {
        for (int i = 0; i < K; i++) {
            scanf("%s %d %d", s, &x, &y);
            D[i] = Patient(x, y, s);
        }
        int aWorking[32] = {}, bWorking[32] = {};
        int aFinTime[32] = {}, bFinTime[32] = {};
        int aPid[32], bPid[32], aUsed[32] = {}, bUsed[32] = {};
        int preTime = -1, pid = 0;
        
        memset(aPid, -1, sizeof(aPid));
        memset(bPid, -1, sizeof(bPid));
        
        priority_queue<int, vector<int>, greater<int> > timeline;
        timeline.push(ST_T * 60);
        while (!timeline.empty()) {
            int now = timeline.top();
            timeline.pop();
            if (now == preTime) continue;
            preTime = now;
            vector<int> A2B;
            for (int i = 0; i < N; i++) {
                if (aWorking[i] && aFinTime[i] <= now) {
                    aWorking[i] = 0;
                    if (aPid[i] >= 0) {
                        A2B.push_back(aPid[i]);
                        aWorking[i] = 1;
                        aFinTime[i] = now + PA_T;
                        aPid[i] = -1;
                        timeline.push(now + PA_T);
                    }
                }
            }
            for (int i = 0; i < M; i++) {
                if (bWorking[i] && bFinTime[i] <= now) {
                    bWorking[i] = 0;
                    if (bPid[i] >= 0) {
                        bWorking[i] = 1;
                        bFinTime[i] = now + PB_T;
                        bPid[i] = -1;
                        timeline.push(now + PB_T);
                    }
                }
            }
            for (int i = 0; i < A2B.size(); i++) {
                int x = A2B[i];
                for (int j = 0; j < M; j++) {
                    if (bWorking[j] == 0) {
                        bWorking[j] = 1;
                        bFinTime[j] = PAB_T + now + D[x].pb;
                        bPid[j] = x, bUsed[j] += D[x].pb;
                        D[x].bid = j;
                        D[x].bBegin = now + PAB_T, D[x].bEnd = bFinTime[j];
                        timeline.push(bFinTime[j]);
                        break;
                    }
                }
            }
            for ( ; pid < K; pid++) {
                int ok = 0;
                for (int i = 0; i < N; i++) {
                    if (aWorking[i] == 0) {
                        aWorking[i] = 1;
                        aFinTime[i] = now + D[pid].pa;
                        aPid[i] = pid, aUsed[i] += D[pid].pa;
                        D[pid].aid = i;
                        D[pid].aBegin = now, D[pid].aEnd = aFinTime[i];
                        timeline.push(aFinTime[i]);
                        ok = 1;
                        break;
                    }
                }
                if (!ok)
                    break;
            }
        }
        
        int ST = 0x3f3f3f3f, ED = 0;
        puts(" Patient          Operating Room          Recovery Room");
        puts(" #  Name     Room#  Begin   End      Bed#  Begin    End");
        puts(" ------------------------------------------------------");
        for (int i = 0; i < K; i++) {
            printf("%2d  %-9s %2d  %3d:%02d  %3d:%02d    %3d  %3d:%02d  %3d:%02d\n",
                   i+1, D[i].name.c_str(), D[i].aid+1,
                   D[i].aBegin/60, D[i].aBegin%60, D[i].aEnd/60, D[i].aEnd%60, D[i].bid+1,
                   D[i].bBegin/60, D[i].bBegin%60, D[i].bEnd/60, D[i].bEnd%60);
            ST = min(ST, D[i].aBegin);
            ED = max(ED, D[i].bEnd);
        }
        puts("");
        puts("Facility Utilization");
        puts("Type  # Minutes  % Used");
        puts("-------------------------");
        for (int i = 0; i < N; i++) {
            printf("%-4s %2d %7d %7.2lf\n", "Room", i+1, aUsed[i], (double) aUsed[i]*100/(ED - ST));
        }
        for (int i = 0; i < M; i++) {
            printf("%-4s %2d %7d %7.2lf\n", "Bed", i+1, bUsed[i], (double) bUsed[i]*100/(ED - ST));
        }
        puts("");
    }
    return 0;
}
/*
 
 */