A1017 Queueing at Bank (25 分| 模拟，附詳細注釋，邏輯分析)

寫在前面

• 思路分析
  • n個客戶， k個視窗
    • 已知每個客戶到達時間和需要時長，如果有視窗就依次過去，沒有視窗就在黃線外等候。求客戶平均等待時長
      • 黃線外隻有1個隊伍，先來先服務
      • 銀行開放時間為8點到17點，8點之前不開門， 8點之前來的人要等待，在17點後來的人不被服務。
  • 實作分析：
    • 客戶結構體node，到達時間、需要服務時長
      • 先将所有滿足條件的（到來時間點在17點之前）客戶放入數組，數組長度就是需要服務的客戶個數
      • window數組表示某個視窗的結束時間
        • 客戶到，有空閑視窗，等待時間為0，重新整理視窗結束時間
        • 客戶到，無空閑視窗，循環比較等待時間最小的一個，重新整理視窗結束時間
    • 開始所有視窗值都為8點整。對所有客戶先進行排序，按來的時間早晚排序，之後再先來先服務
      • 時間暫時化解成秒數，便于計算
      • 如果1個可以被服務的客戶都沒有，輸出0.0
• 題目基礎，細節處理耗費時間
  • 學習ing

測試用例

• input:
  7 3
  07:55:00 16
  17:00:01 2
  07:59:59 15
  08:01:00 60
  08:00:00 30
  08:00:02 2
  08:03:00 10
  output:
  8.2
             

ac代碼

• #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  struct node
  {
      int come, time;
  } tmpcustomer;
  bool cmp1(node a, node b)
  {
      return a.come < b.come;
  }
  int main()
  {
      int n, k;
      scanf("%d%d", &n, &k);
      vector<node> custom;
      for(int i = 0; i < n; i++)
      {
          int hh, mm, ss, time;
          scanf("%d:%d:%d %d", &hh, &mm, &ss, &time);
          int cometime = hh * 3600 + mm * 60 + ss;
          // 17點後
          if(cometime > 61200) continue;
          tmpcustomer = {cometime, time * 60};
          custom.push_back(tmpcustomer);
      }
      sort(custom.begin(), custom.end(), cmp1);
  
      // 初始化為早8點
      vector<int> window(k, 28800);
      double result = 0.0;
  
      for(int i = 0; i < custom.size(); i++)
      {
          int tmpInx = 0, minfinish = window[0];
          // window數組表示某個視窗的結束時間，每1個客戶到來的時候，選擇最早結束時間的視窗
          for(int j = 1; j < k; j++)
          {
              if(minfinish > window[j])
              {
                  minfinish = window[j];
                  tmpInx = j;
              }
          }
  
          // 如果最早結束時間比他晚，累加等待的時間，更新window的值
          if(window[tmpInx] <= custom[i].come)
              window[tmpInx] = custom[i].come + custom[i].time;
          else
          {
              result += (window[tmpInx] - custom[i].come);
              window[tmpInx] += custom[i].time;
          }
      }
  
      if(custom.size() == 0)
          printf("0.0");
      else
          printf("%.1f", result / 60.0 / custom.size());
      return 0;
  }