a513 - 最大值
題目描述
題目要求處理一系列的數字，可以插入數字到序列中，也可以查詢並刪除序列中的最大值。最後輸出剩餘序列，如果序列為空則輸出 "It's empty!"。
解題思路
這題的核心在於維護一個序列，並能快速找到並刪除最大值。使用優先佇列 (priority queue) 是一個非常適合的資料結構，因為它能自動將最大值放在頂端，並且刪除操作的時間複雜度較低。
程式碼首先讀取測試案例的數量，然後對於每個案例，讀取初始序列的長度和操作的數量。使用一個優先佇列 q 來儲存序列中的數字。對於每個操作，如果操作類型為 1，則讀取一個數字並將其插入到優先佇列中。如果操作類型為 2，則檢查優先佇列是否為空，如果非空，則輸出優先佇列的頂端元素（最大值），並將其從優先佇列中刪除。如果優先佇列為空，則輸出 "It's empty!"。
在處理完所有操作後，輸出剩餘的序列。如果優先佇列為空，則輸出 "It's empty!"，否則，按照從大到小的順序輸出優先佇列中的所有元素。
複雜度分析
- 時間複雜度: O(m log n)，其中 m 是操作的數量，n 是序列的最大長度。插入和刪除操作在優先佇列中的時間複雜度都是 O(log n)。
- 空間複雜度: O(n)，優先佇列最多儲存 n 個元素。
程式碼
#include <iostream>
#include <queue>
using namespace std;
int ca,n,m,k,is;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> ca;
for(int i=1;i<=ca;++i){
cin >> n >> m;
priority_queue <int> q;
while(n--){
cin >> k;
q.push(k);
}
cout << "Case " << i << ":\n";
while(m--){
cin >> is;
if(is==2){
if(q.empty()){
cout << "It's empty!\n";
}
else{
cout << "Max: "<< q.top() << "\n";
q.pop();
}
}
else{
cin >> k;
q.push(k);
}
}
if(q.empty()){
cout << "It's empty!\n";
}
else{
while(q.empty()==0){
cout << q.top() << " ";
q.pop();
}
cout << "\n";
}
}
}