1026 Table Tennis (30 分)(C语言实现)（PAT）

本文主要是介绍1026 Table Tennis (30 分)(C语言实现)（PAT），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目解析

维护两个队列，分别为普通用户的编号序列，i以及VIP用户的编号序列。

#include <stdio.h>
#include <stdlib.h>
#define MaxCustomerNum 10000
#define MaxWindowNum 101
#define EmptyTable -1
#define VIP 1
#define NONVIP 0struct CNodes
{int aTime, pTime, sTime, tag;
}C[MaxCustomerNum];
struct WNodes
{int num, servenum, tag;
}W[MaxWindowNum];
typedef struct QNodes *Queue;
struct QNodes
{int data[MaxCustomerNum];int front, rear;
};
int comp1(const void *a, const void *b)
{return ((const struct CNodes*)a)->aTime > ((const struct CNodes *)b)->aTime? 1 : -1;
}
int comp2(const void *a, const void *b)
{return ((const struct CNodes*)a)->sTime > ((const struct CNodes *)b)->sTime? 1 : -1;
}
void addQ(Queue Q, int X)
{Q->data[Q->rear++] = X;
}
int deleteQ(Queue Q)
{return Q->data[Q->front++];
}
int IsEmpty(Queue Q)
{return Q->front == Q->rear;
}int main()
{int N, hour, min, sec, cnt = 0, t, vipt, temp, time = 8*60*60, p;scanf("%d", &N);Queue Q[2];for(int i=0; i<2; i++ ){Q[i] = (Queue)malloc(sizeof(struct QNodes));Q[i]->front = Q[i]->rear = 0;}
/*结构数组C存储所有客户的到达时间，服务时间，服务持续时间等*/for(int i=0; i<N; i++ ){scanf("%d:%d:%d %d %d", &hour, &min, &sec, &p, &C[i].tag);if(p>120) p = 120;C[i].pTime = p*60;C[i].aTime = (hour*60+min)*60 + sec;C[i].sTime = -1;}/*按照到达时间进行排序*/qsort(C, N, sizeof(struct CNodes), comp1);/*初始化窗口结构数组*/scanf("%d %d", &t, &vipt);for(int i=1; i<=t; i++ ){W[i].num = 0;W[i].servenum = EmptyTable;W[i].tag = NONVIP;}for(int i=0; i<vipt; i++ ){scanf("%d", &temp);W[temp].tag = VIP;}for(; time<21*3600; time++){while(C[cnt].aTime<=time && cnt<N){addQ(Q[C[cnt].tag], cnt);cnt++;}for(int i=1; i<=t; i++ ){if(W[i].servenum!=EmptyTable){if(--C[W[i].servenum].pTime == 0) W[i].servenum = EmptyTable;}}if(IsEmpty(Q[VIP])&&IsEmpty(Q[NONVIP])) continue;for(int i=1; i<=t; i++ ){if(!IsEmpty(Q[VIP]) && W[i].servenum == EmptyTable && W[i].tag){W[i].servenum = deleteQ(Q[VIP]);W[i].num++;C[W[i].servenum].sTime = time;}}if(IsEmpty(Q[VIP])){for(int i=1; i<=t; i++ ){if(IsEmpty(Q[NONVIP])) break;else{if(W[i].servenum == EmptyTable){W[i].servenum = deleteQ(Q[NONVIP]);W[i].num++;C[W[i].servenum].sTime = time;}}}}else{for(int i=1; i<=t; i++ ){if(W[i].servenum == EmptyTable){if(!IsEmpty(Q[VIP]) && !IsEmpty(Q[NONVIP])){if(C[Q[VIP]->data[Q[VIP]->front]].aTime < C[Q[NONVIP]->data[Q[NONVIP]->front]].aTime)W[i].servenum = deleteQ(Q[VIP]);else W[i].servenum = deleteQ(Q[NONVIP]);}else if(!IsEmpty(Q[VIP])) W[i].servenum = deleteQ(Q[VIP]);else if(!IsEmpty(Q[NONVIP])) W[i].servenum = deleteQ(Q[NONVIP]);else break;W[i].num++;C[W[i].servenum].sTime = time;}}}}qsort(C, N, sizeof(struct CNodes), comp2);for(int i=0; i<N; i++ ){if(C[i].sTime!=-1){printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", C[i].aTime/3600, C[i].aTime/60-60*(C[i].aTime/3600), C[i].aTime%60,\C[i].sTime/3600, C[i].sTime/60-60*(C[i].sTime/3600), C[i].sTime%60, (C[i].sTime-C[i].aTime+30)/60);}}for(int i=1; i<t; i++ ) printf("%d ", W[i].num);printf("%d\n", W[t].num);for(int i=0; i<2; i++ ) free(Q[i]);return 0;
}