PAT1017 Queueing at Bank

　　本题解题思路是先对输入进行按照时间到达的先后顺序进行排序，然后依次模拟到达窗口，对每个窗口有一个空闲时间，表示该窗口能够处理下一个客户的最近时间。将每个客户到达的时间按照格式转化成秒，用户的时间total和窗口的空闲时间比较，若大于则说明用户到达时窗口是空闲的，就不需要等待；若小于则需要遍历所有窗口，查找空闲窗口，若不存在空闲窗口，则计算所有窗口中最近空闲时间的那个窗口，对其进行更新时间。

　　　　代码如下：

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 using namespace std;
  5 typedef struct Record
  6 {
  7     int hour;
  8     int minute;
  9     int second;
 10     int wait_time;
 11     int total;
 12 }Record_record;
 13 
 14 typedef struct Waitline
 15 {
 16     int end_time;
 17 }Waitline_record;
 18 
 19 vector <Record_record> record_list;
 20 vector <Waitline_record> wait_list;
 21 
 22 
 23 bool compare(const Record_record &a, const Record_record &b)
 24 {
 25     if (a.total < b.total)
 26     {
 27         return true ;
 28     }
 29     else
 30     {
 31         return false ;
 32     }
 33 }
 34 
 35 int cal_min_wait()
 36 {
 37     int i;
 38     int min = wait_list[0].end_time;
 39     int index = 0;
 40     for (i = 0; i < wait_list.size(); i++ )
 41     {
 42         if (min > wait_list[i].end_time)
 43         {
 44             min = wait_list[i].end_time;
 45             index = i;
 46         }
 47     }
 48 
 49     return index;
 50 }
 51 
 52 int main()
 53 {
 54     int i,j;
 55     int num,window_num;
 56     int hour,minute,second;
 57     int wait_time;
 58     int count = 0;
 59     int total_wait_time = 0;
 60     int rest_time;
 61     int min;
 62     //enter the num
 63     cin>>num>>window_num;
 64 
 65     for (i = 0; i < num; i++)
 66     {
 67         Record_record record;
 68         scanf( "%d:%d:%d" ,&hour,&minute,&second);
 69         scanf( "%d" ,&wait_time);
 70 
 71         if (hour>=17 && (minute != 0 || second != 0))
 72         {
 73             continue ;
 74         }
 75 
 76         record.hour = hour;
 77         record.minute = minute;
 78         record.second = second;
 79         record.total = hour*3600 + minute*60+second;
 80         record.wait_time = wait_time*60;
 81         record_list.push_back(record);
 82         count++;
 83     }
 84 
 85     for (i = 0; i < window_num; i++)
 86     {
 87         Waitline_record wait_window;
 88         wait_window.end_time = 28800;
 89         wait_list.push_back(wait_window);
 90     }
 91 
 92     sort(record_list.begin(),record_list.end(),compare);
 93 
 94     for (i = 0; i < count; i++)
 95     {
 96         //在8点前都算等待时间
 97         if (record_list[i].hour < 8)
 98         {
 99             total_wait_time += 28800-record_list[i].total;
100             record_list[i].total = 28800;
101         }
102         for (j = 0; j < window_num; j++)
103         {
104             //判断到达时间在某窗口空闲时间之前，还是之后，之前的话查找其他窗口是否空闲；    
105             if (record_list[i].total >= wait_list[j].end_time)
106             {
107                 //若该窗口空闲，无需等待，则该用户在此窗口处理，更新此窗口的空闲时间节点
108                 wait_list[j].end_time = record_list[i].total+record_list[i].wait_time;
109                 break ;
110             }
111 
112         }
113         //若该用户到达时没有空闲窗口
114         if (j == window_num)
115         {
116             //等待空闲时间节点最短的那个窗口
117             min = cal_min_wait();
118             //等待直到时间最近窗口空闲
119             total_wait_time += wait_list[min].end_time - record_list[i].total;
120             //更新窗口的最近空闲时间
121             wait_list[min].end_time += record_list[i].wait_time;
122         }
123 
124     }
125 
126     double wait_min =(double ) total_wait_time /60;
　　　　 double average;
　　　　  if(count != 0)
127       average = wait_min / count;
128 　　 else
　　　　　　average = 0.0;

129     printf( "%.1lf
" ,average);
130 
131     return 0;
132 }