【Pat 1017】Queueing at Bank

一、摘要

Pat 1017题目银行排队。

看了别人的解题思路做的，自己做个笔记。

二、资源

http://www.cnblogs.com/Rafy/archive/2012/03/20/2408419.html

三、总结思路

首先分析题目：三个服务窗口，N个客户，07:55:00 16（到达时间服务时间），等于进程的FIFO进程调度
服务时间限制：8:00-17:00,17：00以后到来的客户为无效客户，8:00之前到达的得等到开门
主要程序流程图

四、代码

View Code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct{
  5     int hour;
  6     int minutes;
  7     int seconds;
  8     int process;
  9 
 10     int start;
 11     int end;
 12     int valid;
 13 }customer;
 14 
 15 typedef struct{
 16     int id;//当前窗口服务的客户ID
 17     int busy;
 18 }window;
 19 
 20 int getStart(int hh,int mm,int ss)
 21 {
 22     int time_a=0,time_b=0;
 23     if(hh>=17){ return 32401;}
 24     time_a=hh*3600+mm*60+ss;
 25     time_b=8*3600;
 26 
 27     return (time_a-time_b);
 28 }  
 29 
 30 int comp(const void *a, const void *b)
 31 {
 32     customer tmp_a,tmp_b;
 33 
 34     tmp_a=*((customer *)a);
 35     tmp_b=*((customer *)b);
 36 
 37     if (tmp_a.hour==tmp_b.hour)
 38     {
 39         if(tmp_a.minutes==tmp_b.minutes){
 40             return tmp_a.seconds>tmp_b.seconds;
 41         }
 42         else return tmp_a.minutes>tmp_b.minutes;
 43     }
 44     else return tmp_a.hour>tmp_b.hour;
 45 }
 46 
 47 int isAllWindowBusy(window * wd,int len)
 48 {
 49     int i;
 50 
 51     for (i=0;i<len;i++)
 52     {
 53         if(wd[i].busy==0) return i;
 54     }
 55     return -1;
 56 }
 57 
 58 
 59 int main()
 60 {
 61     int i,n,k,empty,j;
 62     customer *ct;
 63     window * wd;
 64     int time;
 65     long sum;
 66 
 67     while(scanf("%d %d",&n,&k)!=EOF)
 68     {
 69         ct=(customer*)malloc(sizeof(customer)*n);
 70         for (i=0;i<n;i++)
 71         {
 72             scanf("%d:%d:%d %d",&ct[i].hour,&ct[i].minutes,&ct[i].seconds,&ct[i].process);
 73             ct[i].start=getStart(ct[i].hour,ct[i].minutes,ct[i].seconds);
 74             if(ct[i].start==32401) ct[i].valid=0;
 75             else ct[i].valid=1;
 76         }
 77         qsort(ct,n,sizeof(customer),comp);
 78         wd=(window*)malloc(sizeof(window)*k);
 79         for (i=0;i<k;i++)
 80         {
 81             wd[i].busy=0;
 82         }
 83 
 84         i=time=0;
 85         empty=-1;
 86         for (;i<n;)
 87         {
 88             while((empty=isAllWindowBusy(wd,k))!=-1&&i<n)
 89             {
 90                 if (ct[i].valid&&ct[i].start<=time)
 91                 {
 92                     wd[empty].id=i;    
 93                     wd[empty].busy=1;
 94                     ct[i].end=time;
 95                     i++;
 96                 }
 97                 else if(!ct[i].valid) i++;
 98                 else break;
 99             }
100             time++;
101 
102             for (j=0;j<k;j++)
103                 if (wd[j].busy&&ct[wd[j].id].end+ct[wd[j].id].process*60==time)
104                     wd[j].busy=0;
105         }
106 
107         for (k=sum=i=0;i<n;i++)
108             if(ct[i].valid) {sum+=ct[i].end-ct[i].start;k++;}
109         printf("%.1f\n",(double)sum/(60.0*k));
110     }
111 
112     return 0;
113 }