a706:
快餐店排隊 (fastfood)
Content
快餐店最近推出期間限定的乾炒牛河餐跟薯樂可樂，一時間大排長龍。為加快點餐速度，快餐店有 N 個櫃枱同時運作（ 2≤N≤105 ），左至右編號 0 至 N−1 。現時，第 i 個有 a[i] 人排隊（ 1≤a[i]≤104 ）。此後有 Q 個時刻（ 1≤Q≤5×105 ），順序發生若干件事，分為以下兩類：
close i：因人手不足，i號櫃枱自此停止服務。此時，若該櫃枱左右兩側（不必相鄰）皆有其他櫃枱仍然運作，則原於該櫃枱排隊的一半人（向上取整）會移步左方最近的未停用櫃枱，另一半（向下取整）會移步右方最近的未停用櫃枱；若僅一側有未停用櫃枱，則全隊人移步該方向最近的未停用櫃枱。此事不會於同一櫃枱重複發生，因為一旦停用就不會重開。同時，餐廳保證停用後仍總有至少兩個櫃枱運作。welcome：一個新客人來到，走向最少人排隊的未停用櫃枱跟隊。若多於一條隊同時屬最少人，則他選擇最左邊的一條，因為入口在左邊。
餐廳希望順序記錄每位新客人選擇的櫃枱編號。
Input
本題數據規模較大，請注意輸入輸出耗時。
首行有獨一個正整數 N，表示櫃枱數。
其下一行有 N 個正整數，依序為 a[0],a[1],…,a[N−1]，表示各櫃枱目前的排隊人數。
其下一行有獨一個正整數 Q，表示將發生的事件數。
其下有 Q 行，每行以一個字串起首，表示事件種類，衹有 close 和 welcome 兩種。若前述字串為 close，則同一行後面有另一個整數 i 表示將關閉的櫃枱號；否則，該行沒有其他內容。
Output
對應輸入的每行 welcome，輸出一行。該行有獨一個整數，表示新來顧客前往排隊的櫃枱號。
Sample Input
#1
5 3 1 4 1 5 13 welcome welcome close 1 welcome close 4 welcome welcome welcome welcome close 0 welcome close 2 welcome
Sample Output
#1
1 3 3 0 0 2 0 3 3
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <10M
不公開 測資點#5 (10%): 1.0s , <10M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.5s , <10M
不公開 測資點#8 (10%): 1.5s , <10M
不公開 測資點#9 (10%): 2.0s , <10M
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <10M
不公開 測資點#5 (10%): 1.0s , <10M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.5s , <10M
不公開 測資點#8 (10%): 1.5s , <10M
不公開 測資點#9 (10%): 2.0s , <10M
Hint ：
對於 30 分的測資，有 N≤103, Q≤103 。
對於另 30 分的測資，事件必定是在若干次 close 之後有唯一一次 welcome。
另 40 分的測資沒有額外限制。
Tags:
出處:
MOIC 2022
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||