d004: 排隊買口罩
Tags :
Accepted rate : 2人/4人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-25 22:46

Content

萊茵國由於冠冠疫情關係導致口罩短缺,政府決定要從相關工廠統一配給口罩至藥局,再由藥局在各地點販賣口罩,每天每個時間的口罩完成數量不定,到貨數量多少就當場賣多少數量,隨到隨賣,因此負責販賣口罩的藥局就想了一個販賣的方法。


首先藥局會先在某個時間點開放讓民眾領取號碼牌,號碼牌從1開始發放,有多少民眾來領就給多少號碼牌,每位民眾領完號碼牌後將會先去處理自己的事情,等到有空時再來購買。


針對前來購買的民眾,如果藥局內還有沒賣完的口罩,將會依照民眾到達的順序直接販售,除非口罩已經賣完,那麼藥局將會依照民眾到達的順序,一位一位民眾依照號碼牌大小順序讓民眾排好,等工廠配給的口罩到了後,再按照排好的順序依序販售,由於口罩短缺的關係,每位民眾僅能購買一個口罩。


工廠口罩到貨的時間與數量皆不固定,再加上有些拿到號碼牌的人都是等他有空時才來購買口罩,因此每個人前往藥局購買口罩所花的時間成本都不一樣,有些來購買的民眾非常在乎他所花的時間成本,政府非常在乎每個人的意見,因此只要某位民眾說他想要知道他所花的時間成本,藥局相關人員就必須將成本告知,請你寫一個程式來幫藥局負責人計算時間成本。


首先,藥局負責人會按照時間順序紀錄前來排隊民眾的基本資料與到貨的口罩資料,每筆資料共有兩個數字a與b,其中 a 代表紀錄資料的類型,b代表號碼牌數字或是口罩的數量,總共有三種類型的資料組合。
(一) a = 1 代表該位民眾前來購買口罩,這位民眾對他花的成本沒有意見,b則代表該位民眾的號碼牌數字。
(二) a = 2 代表該位民眾前來購買口罩,b也代表該位民眾的號碼牌數字,這位民眾希望知道他買到口罩時所花的成本,因此必須在該位民眾買到口罩時馬上算出成本並且輸出。
(三) a = -1 代表在這個時間點有口罩到貨了,b 則代表到貨的口罩數量,只要現在有人正在排隊買口罩,便可以馬上開始販賣。

 

成本計算方式如下:
(一) 當沒有口罩可以販賣的時候,藥局人員會依序將到到達藥局的人員按照號碼牌數字大小排好,為了怕有人會插隊,藥局人員會先看到這位民眾該安插的位置,先將安插位置後的民眾每人往後移動一個位置後,再讓該民眾進入,如果該位民眾後方有 n 位民眾,每移動一位民眾會花1 個成本,則尚在隊伍當中的每位民眾總共會花n個等待成本。
(二) 當有口罩到貨時,就可以開始販賣口罩。販賣每位民眾一個口罩需要讀取個人資料晶片,因此算 1 個成本;當販賣完到貨的口罩後,還有民眾沒有買到口罩,這些民眾需要往前移動到排隊的開頭,假設這次總共賣的m個口罩,則每位民眾皆須花費往前移動m個成本,假設有k位民眾需要移動,則尚在隊伍的民眾總共需花費k*m 個等待成本。
(三) 每位有意見的民眾所要計算的成本,從藥局負責人將他安插到隊伍位置後才開始計算,安插這位民眾要花的成本不算在這位民眾整體成本當中。
(四) 當藥局尚有口罩可以販賣時,每位民眾隨到隨賣,僅負擔讀取晶片需要的1個成本。

Input

輸入檔當中會有多行資料,每行資料皆由兩個數字a、b組成;a 的值僅有1,2,-1 三種可能;若 b 代表號碼牌的數字,1<=b<=10000,若b 代表到貨的口罩數量,則 1<= b <=1000。

Output

針對每位想要知道買口罩所花時間成本的民眾,在該位民眾購買到口罩後,請輸出他所花的時間成本 S,S至少為 1。

Sample Input
1 10
2 2
-1 2
2 20
1 17
-1 3
2 100
Sample Output
1
3
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (12%): 1.0s , <1K
公開 測資點#1 (12%): 1.0s , <1K
公開 測資點#2 (12%): 1.0s , <1K
公開 測資點#3 (12%): 1.0s , <1K
公開 測資點#4 (13%): 1.0s , <1K
公開 測資點#5 (13%): 1.0s , <1M
公開 測資點#6 (13%): 1.0s , <1K
公開 測資點#7 (13%): 1.0s , <1M
Hint :
Tags:
出處:
[管理者:
zero (管理員)
]


ID User Problem Subject Hit Post Date
20
Eason0165 (EasonLearner)
d004
70 2023-11-06 01:41