a091 - 今晚打老虎
題目描述
題目要求實作一個可以插入數字並查詢最大值和最小值的系統。每次查詢最大值或最小值後，該值會從集合中移除。
解題思路
這題的核心在於維護一個可以快速查詢最大值和最小值的資料結構，並且在查詢後能夠刪除該元素。std::multiset 是一個很好的選擇，因為它可以儲存重複的元素，並且提供 begin() 和 rbegin() 方法來快速存取最小值和最大值。插入操作直接使用 insert()，最大值查詢使用 *ans.begin()，最小值查詢使用 *(--ans.end())，刪除操作使用 erase()。
複雜度分析
- 時間複雜度: O(log N)
- 插入 (insert): O(log N)
- 查詢最大值 (查詢最小值): O(1)
- 刪除最大值 (刪除最小值): O(log N)
其中 N 是
multiset中元素的數量。
- 空間複雜度: O(N)
- 儲存所有插入的數字需要 O(N) 的空間。
程式碼
#include <stdio.h>
#include <set>
using namespace std;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
multiset <int> ans;
int n,is;
int main(){
while(is=read()){
if(is==1){
n=read();
ans.insert(n);
}
else if(is==3){
write(*ans.begin());
putchar_unlocked('\n');
ans.erase(ans.begin());
}
else{
write(*(--ans.end()));
putchar_unlocked('\n');
ans.erase(--ans.end());
}
}
}