UVa 540 Team Queue

UVa 540 Team Queue
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Team Queue

Time Limit: Unknown Memory Limit: Unknown
Total Submission(s): Unknown Accepted Submission(s): Unknown



https://uva.onlinejudge.org/i…


Accepted Code

// Author : Weihao Long
// Created : 2018/01/17
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define OK                1
#define ERROR             0
#define TRUE              1
#define FALSE             0
#define INFEASIBLE       -1
#define OVERFLOW         -2
typedef int QElemType;
struct QNode {
QElemType data;
struct QNode *next;
};
typedef struct {
QElemType team;
QNode *front;
QNode *rear;
}LinkQueue;
int InitQueue(LinkQueue *Q);
int EnQueue(LinkQueue *Q, QElemType e);
int DeQueue(LinkQueue *Q, QElemType *e);
int ClearQueue(LinkQueue *Q);
int DestroyQueue(LinkQueue *Q);
int people[1000007];
LinkQueue queue[1000007];
int main() {
int t;
int kase = 1;
while (scanf("%d", &t) != EOF) {
if (!t) {
break;
}
printf("Scenario #%d\n", kase  );
int m;
memset(people, 0, sizeof(people));
memset(queue, 0, sizeof(queue));
int qh = 1, qt = 1;
for (int i = 1; i <= t; i  ) {
int cap;
scanf("%d", &cap);
while (cap--) {
scanf("%d", &m);
people[m] = i;
}
}
char cmd[10];
while (scanf("%s", cmd) != EOF) {
if (!strcmp(cmd, "STOP")) {
putchar('\n');
break;
}
else if (!strcmp(cmd, "ENQUEUE")) {
int flag = 0;
scanf("%d", &m);
int team = people[m];
for (int i = qh; i < qt; i  ) {
if (queue[i].team == team) {
flag = i;
break;
}
}
if (flag) {
LinkQueue T;
T = queue[flag];
EnQueue(&T, m);
queue[flag] = T;
}
else {
LinkQueue T;
InitQueue(&T);
T.team = team;
EnQueue(&T, m);
queue[qt  ] = T;
}
}
else if (!strcmp(cmd, "DEQUEUE")) {
LinkQueue T;
T = queue[qh];
DeQueue(&T, &m);
printf("%d\n", m);
queue[qh] = T;
if (T.front == T.rear)
qh  ;
}
}
}
return 0;
}
int InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
if (!Q->front) {
exit(OVERFLOW);
}
Q->front->next = NULL;
return OK;
}
int EnQueue(LinkQueue *Q, QElemType e) {
QNode *p = (QNode *)malloc(sizeof(QNode));
if (!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
return OK;
}
int DeQueue(LinkQueue *Q, QElemType *e) {
if (Q->front == Q->rear) {
return ERROR;
}
QNode *p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) {
Q->rear = Q->front;
}
free(p);
return OK;
}
int ClearQueue(LinkQueue *Q) {
QNode *p, *q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q = p;
p = p->next;
free(q);
}
return OK;
}
int DestroyQueue(LinkQueue *Q) {
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}

Notes

題意:
團隊排隊,每次 ENQUEUE 先檢查隊伍裡有沒有自己人,若有,則插到自己人的最後,否則排到隊尾。出隊 DEQUEUE 按正常規則來。

思路:
1.用一個陣列 queue 來存佇列,佇列中每個元素包含三個資訊:團隊編號、團隊頭指標、團隊尾指標。並用 qh 標誌隊首,用 qt 標誌隊尾。
2.每次 ENQUEUE 先檢查 queue 中有沒有自己所屬團隊,若有,插到團隊的最後。若沒有,則在 queue 的最後新建一個團隊,並插入這個人,然後把隊尾標誌後移。
3.每次 DEQUEUE 就把 queue 隊首的團隊中的第一個人輸出,如果該團隊空了,就把隊首標誌後移。

感受:
這題如果只用一個佇列來做(佇列中的元素包含兩個資訊:某人的編號、他所屬團隊),就需要便歷整個隊伍來查詢自己所屬團隊,時間開銷太大,過不了。
然後改進一下得到如上程式碼,用 queue 存團隊編號以及該團隊的頭、尾指標,這樣一來主佇列大幅縮短,遍歷的時間開銷就大幅降低了。

附:

相關文章

程式語言 最新文章