problem
L3-002 特殊堆栈 (30分) 堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。
输入格式： 输入的第一行是正整数 N（≤10 5 ）。随后 N 行，每行给出一句指令，为以下 3 种之一：
Push key Pop PeekMedian 其中 key 是不超过 10 5 的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian 表示“取中值”。
输出格式： 对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian 操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。
输入样例： 17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop 输出样例： Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid
problem
维护一个栈(1e5)，支持pop，push和取中间值(第n/2小元)即需要nlogn的维护中位数，想到了multiset，但是迭代器输出会TLE可以用vector+二分插入
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 10010;
stack
<int>stk
;
vector
<int>order
;
int main(){
int T
; cin
>>T
;
while(T
--){
string s
; cin
>>s
;
int re
= 0;
if(s
=="Push"){
int x
; cin
>>x
;
stk
.push(x
);
order
.insert(lower_bound(order
.begin(), order
.end(), stk
.top()), stk
.top());
}
if(s
=="Pop"){
if(stk
.size()){
cout
<<stk
.top()<<"\n";
order
.erase(lower_bound(order
.begin(), order
.end(), stk
.top()));
stk
.pop();
}else{
re
= 1;
}
}
if(s
=="PeekMedian"){
if(stk
.size()){
cout
<<order
[(stk
.size()-1)/2]<<endl
;
}else{
re
= 1;
}
}
if(re
)cout
<<"Invalid\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 10010;
stack
<int>stk
;
multiset
<int>se
;
int main(){
int T
; cin
>>T
;
while(T
--){
string s
; cin
>>s
;
int re
= 0;
if(s
=="Push"){
int x
; cin
>>x
;
stk
.push(x
);
se
.insert(x
);
}
if(s
=="Pop"){
if(stk
.size()){
cout
<<stk
.top()<<"\n";
multiset
<int>::iterator pos
= se
.find(stk
.top());
se
.erase(pos
);
stk
.pop();
}else{
re
= 1;
}
}
if(s
=="PeekMedian"){
if(stk
.size()){
int tt
= (stk
.size()+1)/2;
multiset
<int>::iterator it
= se
.begin();
for(int i
= 1; i
< tt
; i
++)it
++;
cout
<<(*it
)<<"\n";
}else{
re
= 1;
}
}
if(re
)cout
<<"Invalid\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 100010;
int stk
[maxn
], top
;
multiset
<int>se
;
int main(){
int T
; cin
>>T
;
while(T
--){
string s
; cin
>>s
;
int re
= 0;
if(s
.size()==4){
int x
; cin
>>x
;
stk
[++top
] = x
;
se
.insert(x
);
}
if(s
.size()==3){
if(top
>=1){
cout
<<stk
[top
]<<"\n";
multiset
<int>::iterator pos
= se
.find(stk
[top
]);
se
.erase(pos
);
top
--;
}else{
re
= 1;
}
}
if(s
=="PeekMedian"){
if(top
>=1){
int tt
= (top
+1)/2;
multiset
<int>::iterator it
= se
.begin();
for(int i
= 1; i
< tt
; i
++)it
++;
cout
<<(*it
)<<"\n";
}else{
re
= 1;
}
}
if(re
)cout
<<"Invalid\n";
}
return 0;
}
