1 #include <iostream> 2 #include<fstream> 3 using namespace std; 4 5 //顾客信息 6 struct Inform 7 { 8 int Arrival; 9 int Typed; 10 int HandleTime; 11 int RestTime; 12 }; 13 14 //链式存储 15 struct Comsumer 16 { 17 Inform data; 18 Comsumer* next; 19 }; 20 21 //队列 22 struct Queue 23 { 24 Comsumer* front; 25 Comsumer* rear; 26 int QueueSize; 27 }; 28 29 //初始化 30 void InitQueue(Queue* Q) 31 { 32 Q->front = Q->rear = (Comsumer*)malloc(sizeof(Comsumer)); 33 if (Q->front == NULL) exit(OVERFLOW); 34 Q->front->next = NULL; 35 Q->QueueSize = 0; 36 } 37 38 //入队 39 void EnQueue(Queue* Q,Inform* e) 40 { 41 Comsumer* s = (Comsumer*)malloc(sizeof(Comsumer)); 42 if (s == NULL) exit(OVERFLOW); 43 44 s->data.Arrival = e->Arrival; 45 s->data.HandleTime = e->HandleTime; 46 s->data.RestTime = e->RestTime; 47 s->data.Typed = e->Typed; 48 49 Q->rear->next = s; 50 Q->rear = s; 51 Q->rear->next = NULL; 52 Q->QueueSize++; 53 } 54 55 //出队 56 void DeQueue(Queue* Q) 57 { 58 if (Q->front == Q->rear) return; 59 60 Comsumer* p = Q->front->next; 61 Q->front->next = p->next; 62 if (Q->rear == p) Q->rear = Q->front; 63 free(p); 64 Q->QueueSize--; 65 } 66 67 //判断队列是否为空 68 bool IsEmpty(Queue* Q) 69 { 70 if (Q->front == Q->rear) return true; 71 72 return false; 73 } 74 75 //更新每个队列 76 void UpdateQueue(Queue* q, int NowTime) 77 { 78 Comsumer* p = q->front->next; 79 if (p != NULL) 80 { 81 p->data.RestTime=p->data.RestTime-NowTime; 82 if (p->data.RestTime <= 0) 83 DeQueue(q); 84 } 85 } 86 87 //选择某个队加入 88 void QueueSelect(Inform*p,Queue*A,Queue*B,Queue*C) 89 { 90 if (p->Typed == 1) 91 { 92 if (A->QueueSize <= C->QueueSize) 93 EnQueue(A, p); 94 else if (A->QueueSize > C->QueueSize) 95 EnQueue(C, p); 96 } 97 else if (p->Typed == 2) 98 { 99 if (B->QueueSize <= C->QueueSize) 100 EnQueue(B, p); 101 else if (B->QueueSize > C->QueueSize) 102 EnQueue(C, p); 103 } 104 } 105 106 //末尾出队 107 void eQueue(Queue* Q) 108 { 109 Comsumer* p = Q->front->next; 110 while (p->next->next != NULL) 111 { 112 p = p->next; 113 } 114 Q->rear = p; 115 } 116 117 //根据其他的调整队伍 118 void UpdateSelect(Queue*A, Queue* B, Queue* C) 119 { 120 //C的人数比A少两个就要找A队尾去C 121 if (A->QueueSize - C->QueueSize >= 2) 122 { 123 Inform* temp = (Inform*)malloc(sizeof(Inform)); 124 temp->Arrival = A->rear->data.Arrival; 125 temp->HandleTime = A->rear->data.HandleTime; 126 temp->RestTime = A->rear->data.RestTime; 127 temp->Typed = A->rear->data.Typed; 128 EnQueue(C, temp); 129 eQueue(A); 130 } 131 //C的人数比B少两个就要找B队尾去C 132 else if (B->QueueSize - C->QueueSize >= 2) 133 { 134 Inform* temp = (Inform*)malloc(sizeof(Inform)); 135 temp->Arrival = B->rear->data.Arrival; 136 temp->HandleTime =B->rear->data.HandleTime; 137 temp->RestTime = B->rear->data.RestTime; 138 temp->Typed = B->rear->data.Typed; 139 EnQueue(C, temp); 140 eQueue(B); 141 } 142 } 143 144 int main() 145 { 146 fstream fp; 147 fp.open("text2.txt", ios::in); 148 149 int N; 150 fp >> N;//读取窗口数 151 152 Queue* A=(Queue*)malloc(sizeof(Queue)); 153 Queue* B = (Queue*)malloc(sizeof(Queue)); 154 Queue* C = (Queue*)malloc(sizeof(Queue)); 155 InitQueue(A); 156 InitQueue(B); 157 InitQueue(C); 158 159 int MaxTime=0; 160 while (!fp.eof()) 161 { 162 //每次读一个进队 163 Inform* temp=(Inform*)malloc(sizeof(Inform)); 164 fp >> temp->Arrival >> temp->Typed >> temp->HandleTime; 165 temp->RestTime = temp->HandleTime;//刚来还有的办理时间就是办理时间 166 int NowTime = temp->Arrival-MaxTime; 167 MaxTime = temp->Arrival; 168 169 //更新三个队列 170 UpdateQueue(A, NowTime); 171 UpdateQueue(B, NowTime); 172 UpdateQueue(C, NowTime); 173 174 //新元素入队 175 QueueSelect(temp, A, B, C); 176 } 177 178 //三个都不为空继续更新并出队 179 while (IsEmpty(A) != true || IsEmpty(B) != true || IsEmpty(C) != true) 180 { 181 //时间增加 182 MaxTime++; 183 //更新三个队列 184 UpdateQueue(A, 1); 185 UpdateQueue(B, 1); 186 UpdateQueue(C, 1); 187 188 UpdateSelect(A, B, C); 189 } 190 cout << MaxTime; 191 }
链式队列