这代码我看都看不懂 _QAQ_
wu~~~~~
by meng_cen @ 2023-09-10 09:32:29
我用队列做的
```cpp
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
using ll=long long;
const int N=1e6+7;
priority_queue<int> q;
priority_queue<int,vector<int>,greater<int>> Q;
int a[N];
vector<int>v;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int b;
cin>>b;
if(q.empty()||b<q.top()){
q.push(b);
}
else Q.push(b);
while(q.size()<Q.size()+1){
q.push(Q.top());
Q.pop();
}
while(q.size()>Q.size()+1){
Q.push(q.top());
q.pop();
}
if(i&1) cout<<q.top()<<"\n";
}
return 0;
}
```
看下行不行 @[KeQingLoveYou](/user/704651)
by meng_cen @ 2023-09-10 09:33:55
复杂度不对。
by hzjnsy @ 2023-09-10 09:36:11
@[hzjnsy](/user/723050) 已经尽力优化过了，使用了快读快出，排序复杂度也是线性的
by KeQingLoveYou @ 2023-09-10 09:43:21
@[meng_cen](/user/797897) 可以了，谢谢，对你的代码进行了一些改进：
```pascal
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
if (maxHeap.empty() || b < maxHeap.top()) {
maxHeap.push(b);
} else {
minHeap.push(b);
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (maxHeap.size() < minHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
if (i & 1) {
cout << maxHeap.top() << "\n";
}
}
return 0;
}
```
采用了两个堆来维护中位数左右的元素，并根据堆的大小关系进行调整
by KeQingLoveYou @ 2023-09-10 09:52:10