PAT1017

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1017

主要思想，是秒数为时钟，判断每一秒种的动作，是否有客户需要处理业务等等，有2点注意下：1，每个客户处理业务时间不能超过一个小时。2，每个在17点前到达的客户都能得到业务办理，即使银行到了关门时间。剩下的就剩模拟了，我的代码中主要用了一个函数来算2个时间之间所差的秒数。

  1 #include<iostream>
  2 #include<string>
  3 #include<vector>
  4 #include<queue>
  5 #include<algorithm>
  6 #include<iomanip>
  7 using namespace std;
  8 
  9 int date2second(string end, string start)
 10 {
 11     int hh(0), mm(0), ss(0);
 12     for(int i=0; i<3; ++i)
 13          if(i == 0)     
 14          { 
 15              ss = (end[6]-start[6])*10 + (end[7]-start[7]);
 16              if(ss < 0 )
 17              {--mm; ss +=60;}
 18          }
 19          else if(i == 1)
 20          {
 21              mm += (end[3]-start[3])*10 + (end[4]-start[4]);
 22              if(mm < 0)
 23                  {--hh; mm+=60;}        
 24          }
 25          else
 26              hh +=  (end[0]-start[0])*10 + (end[1]-start[1]);
 27     int sec = hh*3600+mm*60+ss;
 28     return sec;
 29     /*两个时间点之间差的时间, 用秒数表示返回*/
 30 }
 31 
 32 struct Node
 33 {
 34     int arrives;
 35     int procs;
 36     int waits;
 37 };
 38 /*用秒数老表示时间*/
 39 
 40 bool comp(Node n1, Node n2)
 41 {
 42     if(n1.arrives < n2.arrives)
 43         return true;
 44     else
 45         return false;
 46 }
 47 
 48 int main()
 49 {
 50     int n ,k;
 51     while(cin>>n>>k)
 52     {
 53         if(n == 0 || k == 0)
 54             continue;
 55         vector<queue<Node>> windows(k);
 56         vector<Node> customers;
 57         for(int i=0; i<n; ++i)
 58         {
 59             string atm; int ptm;
 60             cin>>atm>>ptm;
 61             if(atm < "17:00:01")
 62             {
 63                 if(ptm > 60)
 64                     ptm = 60;
 65                 Node n = {date2second(atm, "08:00:00"), ptm*60, 0};
 66                 customers.push_back(n);
 67             }
 68         }
 69         if(customers.empty())
 70             continue;
 71         sort(customers.begin(), customers.end(), comp);
 72         /*排序，保证客户到达顺序的时间连续性*/
 73         queue<Node> cusline;
 74         for(int i=0; i<customers.size(); ++i)
 75             cusline.push(customers[i]);
 76         double num(0);
 77         /*记录有多少客户已经开始或者完成业务*/
 78         int time(0);
 79         /*时钟，以秒为单位*/
 80         double sumtime(0);
 81         /*记录等待时间总和*/
 82         while( !cusline.empty())
 83         {
 84             for(int i=0; i<windows.size(); ++i)
 85                 if(windows[i].empty() && !cusline.empty())
 86                     if(cusline.front().arrives <= time)
 87                     {
 88                         cusline.front().waits = time - cusline.front().arrives;
 89                         sumtime += cusline.front().waits;
 90                         ++num;
 91                         windows[i].push(cusline.front());
 92                         cusline.pop();
 93                     }
 94             /*若窗口空闲且有等待客户，则客户进入*/
 95             ++time;
 96             for(int i=0; i<windows.size(); ++i)
 97                 if(!windows[i].empty())
 98                     if(--windows[i].front().procs == 0)
 99                         windows[i].pop();
100             /*处理每个窗口*/
101         }
102         cout<<fixed<<setprecision(1)<<sumtime/60/num<<endl;
103     }
104     return 0;
105 }