记录编号	588057	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	中位数	最终得分	100
用户昵称	GS53	是否通过	通过
代码语言	C++	运行时间	4.467 s
提交时间	2024-05-14 21:31:57	内存使用	6.72 MiB

//阅读须知：请读完第六行后跳到主函数阅读，有利于理解程序。
//思路：建立一个最大为n/2+1的小根堆，将数据输入小根堆，若堆满就删除堆顶元素，直到数据全部输入。
//若n为偶数，则中位数为堆顶元素，否则中位数为堆顶元素与左孩子和右孩子间更小的那个元素的算数平均值，即（堆顶元素+左孩子与右孩子间更小的那个）/2 
#include<iostream>
#include<cstdio>
using namespace std;
int a[260000]; //定义小根堆a 
int n,s=0,b,t;//n:需处理数据数量，s:堆内元素数量，b:输入媒介（数据中转），t:未处理数据数量 
void swim(int s)//上浮操作，变量s为需要进行上浮的数据，本函数用于插入 
{
while(s>1&&a[s]<a[s/2])
{
swap(a[s],a[s/2]);
s/=2;
}
}
void push(int b)//插入数据 
{
a[++s]=b;
swim(s); //此处s为要上浮的元素在堆中的下标，详见上浮函数swim 
}
void jd()//建立小根堆a，此时a中包含了输入数据中前n/2+1个数据 
{
    for(int i=1;i<=n/2+1;++i) 
    {
        cin>>b;
        push(b); //将b插入至堆中，详见插入函数push 
    }
}
void sink(int k)//下沉操作，k恒为1 
{
while(2*k<=n/2+1)
    {
    int j=2*k;
    if(j+1<=n/2+1&&a[j]>a[j+1])
    {
        j=j+1;
    }
    if(a[k]<=a[j])
    {
        break;
    }
    swap(a[k],a[j]);
    k=j;
    }
}
void pop()//删除数据 
{
    a[1]=a[s--]; //将堆顶替换为堆底元素 
    sink(1); 
}
int main()
{
    freopen("median.in","r",stdin);
    freopen("median.out","w",stdout);
    cin>>n;
    jd(); //建堆，详见建堆函数jd 
    t=n-(n/2+1); //计算未处理数据数量，以免在循环里计算导致超时 
    while(t) //当数据没有处理完时 
    {
        t--; //剩余数据-1 
        cin>>b;
        push(b); //将输入数据b插入堆中，详见插入函数push 
        pop(); //将堆顶（下标最小的不可能为中位数的元素）删除，详见删除函数pop 
    }
    if(n%2) //当n为奇数 
    {
        printf("%0.1f\n",1.0*a[1]);
    }
    else
    {
        printf("%0.1f\n",1.0*(a[1]+min(a[2],a[3]))/2.0);
    }
    return 0;
} //Adam与GS53热心创作