原题链接
首次尝试用chatgpt帮我写注释
code
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; // 声明整数变量 n,用于存储输入序列的长度
cin >> n; // 读入序列长度
// 定义两个优先队列,q1 是最大堆,q2 是最小堆
priority_queue<int> q1; // 最大堆,存储较小的一半元素
priority_queue<int, vector<int>, greater<int>> q2; // 最小堆,存储较大的一半元素
int x; // 用于读入每个元素
cin >> x; // 读入第一个元素
q1.push(x); // 将第一个元素放入最大堆
cout << x << endl; // 输出第一个元素作为初始中位数
// 从第二个元素开始遍历输入序列
for (int i = 2; i <= n; i++) {
cin >> x; // 读入新元素
// 判断新元素应该放入哪个堆
if (x < q1.top()) q1.push(x); // 如果新元素小于最大堆顶,放入最大堆
else q2.push(x); // 否则,放入最小堆
// 平衡两个堆的大小,确保两个堆的大小差不超过1
while (abs(static_cast<int>(q1.size()) - static_cast<int>(q2.size())) > 1) {//std::abs 函数的调用:由于 size() 函数返回的是无符号类型,你需要将其转换为有符号整数类型。
if (q1.size() > q2.size()) {
// 如果最大堆元素多,将最大堆顶元素移动到最小堆
q2.push(q1.top());
q1.pop();
} else {
// 如果最小堆元素多,将最小堆顶元素移动到最大堆
q1.push(q2.top());
q2.pop();
}
}
// 如果目前已读元素个数为奇数,输出中位数
if (i % 2 == 1) {
// 当两个堆的大小一样时,中位数是较大堆的堆顶元素
// 当两个堆的大小不一样时,中位数是元素多的那个堆的堆顶元素
cout << ((q1.size() > q2.size()) ? q1.top() : q2.top()) << endl;
}
}
return 0; // 程序结束
}