題目分析：
本題我第一次嘗試去做的時候用的是優先佇列，但是效率不僅代碼量很大，而且還有測驗樣例過不去，很顯然沒有找到一個好的資料結構來解決這道題目（隨著逐漸的刷PAT甲級的題會發現有時選擇一個好的解題方向真的比一些花里胡哨的技巧重要的多），對于本題，我們需要模擬的是一個去銀行接受服務的程序，銀行有k個視窗，而在8點開門之前所有到達的人都在門外排隊（在8點后到達的人如果有人則需要排隊，視窗中有空位則會選擇最空閑的進行自己的服務），首先我們需要對n個用戶按照到達的時間進行排序，然后建立一個window陣列存放每個視窗結束被占用的的時間（最初始k個視窗都為28800，這是8點轉化成了秒為單位，本題所有的時間都轉化成了秒，方便計算，而上限值則是17點相對的秒數61200秒，用戶在17點之后到達則無法接受服務且不會被加入有效等待人數中），對于用戶佇列，我們每次選擇一個人，這個人將選擇此時k個視窗中時間最小的，模擬用戶接受服務的程序，而這個程序分為兩種情況（1.輪到這個用戶的時候，最小的視窗時間比用戶到達的時間小，則表示在用戶到達之前這個視窗已經空出來了，且沒有人占用它，則這個用戶的等待時間則為0，此時更新這個視窗的時間為該用戶達到時間+該用戶需要服務的時間 2.輪到這個用戶的時候，最小的視窗時間比用戶到達的時間大，則表示用戶在到達的時候最近的一個視窗還正在被占用，則用戶就需要等待的時間為：這個視窗的結束占用時間-用戶到達的時間，然后這個用戶接受服務，則也需要更新這個視窗的結束被占用時間為此時視窗時間+用戶需要服務的時間）對于輸入n為0的情況特判一下
1 #include<iostream> 2 #include<cmath> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 7 struct Node{ 8 int come, time; //記錄每個人到達的時間和需要服務的時間 9 }; 10 11 bool cmp(Node a, Node b){ 12 return a.come < b.come; 13 } 14 15 int main(){ 16 int n, k; 17 while(scanf("%d%d", &n, &k) != EOF){ 18 vector<Node> cus; 19 for(int i = 1; i <= n; i++){ 20 int hh, mm, ss, time; 21 scanf("%d:%d:%d%d", &hh, &mm, &ss, &time); 22 Node peo; 23 peo.come = hh * 3600 + mm * 60 + ss;//到達的時間和被服務時間為秒 24 peo.time = time * 60; 25 if(peo.come <= 61200) cus.push_back(peo); //只有在17點之前的人才會被服務 26 } 27 sort(cus.begin(), cus.end(), cmp); 28 int wait_sum = 0; //總等待時間 29 vector<int> window(k, 28800); //對k個視窗初始化時間為8點 == 28800秒 30 for(int i = 0; i < cus.size(); i++){ //對于所有排隊的用戶一個一個遍歷（模擬尋找視窗的程序 31 int mi = window[0]; 32 int index = 0; 33 for(int j = 0; j < k; j++){ //找到視窗時間最小的 34 if(window[j] < mi){ 35 mi = window[j]; 36 index = j; 37 } 38 } 39 if(window[index] <= cus[i].come){ 40 window[index] = cus[i].come + cus[i].time; 41 }else{ 42 wait_sum += window[index] - cus[i].come; 43 window[index] += cus[i].time; 44 } 45 // cout<<"wait_sum"<<wait_sum<<endl; 46 } 47 if(cus.size() == 0) printf("0.0\n"); 48 else{ 49 printf("%.1lf\n", wait_sum * 1.0 / cus.size() / 60); 50 } 51 } 52 return 0; 53 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138109.html
標籤：其他
上一篇：演算法天天練709：字串轉小寫