题目描述

链接：https://ac.nowcoder.com/acm/problem/50940
来源：牛客网
For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.

翻译就不打了，相信各位大佬都能读懂，那我们直接上分析。

分析

思路一   对顶堆

就是我们可以建立两个堆，来维护比当前值大和小的数（就是以中位数为分界线，一个堆放比它小的数，一个堆放比它大的数），我们将数读进堆后，将它们进行比较，在放较小值的堆中，将较小值的最大值挤入堆顶，在放较大值的堆中，将较大值的最小值挤入堆顶，然后我们知道如果两个堆的大小之差超过1的话，那就说明还没分好，就将一个堆的堆顶弹到另一个堆中，如此反复，到最后差值为一时，说明分好了，弹出即可。 

#include<bits/stdc++.h>
using namespace std;
 
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
  
priority_queue<int> q;
priority_queue<int,vector<int>,greater<int> > p;
int n,t;
  
signed main()
{
    t=read();
    while(t--)
    {
        while(!q.empty()) q.pop();
        while(!p.empty()) p.pop();
        scanf("%d",&n);
        printf("%d ",n);
        n=read();
        printf("%d\n",(n+1)/2);
        for(int i=1;i<=n;i++)
        {
            int x=read();
            if(p.empty()) p.push(x);
            else if(x>=p.top()) p.push(x);
            else q.push(x);
             
            if(p.size()-q.size()>1)
            {
                q.push(p.top());
                p.pop();
            }
            if(p.size()-q.size()<1)
            {
                p.push(q.top());
                q.pop();
            }
            if(i%2)
                printf("%d ",p.top());
            if(!(i%20)) printf("\n");
        }
        puts("");
    }
    return 0;
}

思路二 链表

链表这个东西嘛，指针最大啦。我们开个结构体，分别记录数值，序号，前驱，后继。
然后我们来模拟一下就能发现规律

假设我们一直读到最后一个，中位数那就是（n+1）/2，然后我们将最末尾的删掉，然后如果一直这样，我们可以发现，如果删掉的数在上一个中位数的右边，新的中位数就向前移一个单位，如果删掉的数在上一个中位数的左边，新的中位数就向后移一个单位

此规律一出，那不就简单的有手就行 

#include<bits/stdc++.h>
using namespace std;
 
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+10;
int p;
int kase,zs;
struct data{
	int a,id,nex,pre;
}s[N];
int n;
int ans[N];
int num[N];

bool cmp(const data &x,const data &y)
{
	return x.a>y.a;
}

void dele(int x)//删除当前位置的数 
{
	s[s[x].pre].nex=s[x].nex;
	s[s[x].nex].pre=s[x].pre;
	return ;
}

signed main()
{
	p=read();
	while(p--)
	{
		kase=read();
		n=read();
		for(int i=1;i<=n;i++)
		{
			s[i].a=read();
			s[i].id=i;
		}
		sort(s+1,s+1+n,cmp);
		for(int i=1;i<=n;i++)
		{
			s[i].nex=i+1;
			s[i].pre=i-1;
			num[s[i].id]=i;
		}//常规操作，与邻值查找类似 
		int mid=(n+1)/2;//当前序列中间位置的数 ，也是最开始总的中位数个数 
		cout<<kase<<" "<<mid<<endl;
		int cnt=0;
		for(int i=n;i>=1;i--)//倒着往前 
		{
			if(i%2)//奇数位 
			{
				ans[++cnt]=s[mid].a;//将中位数存起来 
				if(num[i]>=mid) mid=s[mid].pre;//如果这个即将被删的数在原先中位数的左边，那删掉之后，整个序列的中位数应向前移一个单位 
				dele(num[i]);//删掉这个数 
			}
			else
			{
				if(num[i]<=mid) mid=s[mid].nex;//如果这个即将被删的数在原先中位数的右边，那删掉之后，整个序列的中位数应向后移一个单位 
				dele(num[i]);//删掉这个数 
			}
		}
		int k=0;
		for(int i=cnt;i>=1;i--)//倒着输出 
		{
			cout<<ans[i]<<" ";
			k++;//每输出十个，就换行 
			if(k%10==0) cout<<endl;
		}
		if(cnt%10) cout<<endl;//如果超过十个了，也要换行 
	}
	return 0;
}