维护序列的动态中位数
第一次用链表做题。。感觉指针指来指去也挺麻烦的。。
本题链表解法就是用数组模拟出一个链表，然后离线输入所有数，排序，按照输入顺序在链表里删除元素，一次性删掉两个，然后中位数指针对应移动即可
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm> using namespace std;
#define maxn 10004 struct smc{
int val,no;
bool operator<(smc node)const{
return val<node.val;
}
}a[maxn]; int l[maxn],r[maxn],tt,p,n,mid;
int ans[maxn],f[maxn]; int main(){
scanf("%d",&p);
for(tt=;tt<=p;tt++){
scanf("%d%d",&mid,&n);
printf("%d %d\n",tt, n/+);
mid=(+n)/;
for(int i=;i<=n;i++){scanf("%d",&a[i].val);a[i].no=i;}
sort(a+,a++n);
for(int i=;i<=n;i++){l[i]=i-;r[i]=i+;f[a[i].no]=i;}
l[]=l[]=,r[]=;
for(int i=n;i>=;i-=){//一次减掉两个数
ans[i]=a[mid].val;
if(f[i]<mid && f[i-]<=mid) mid=r[mid];
if(f[i]>mid && f[i-]>=mid) mid=l[mid];
if(f[i]==mid){
if(f[i-]>mid) mid=l[mid];
else mid=r[mid];
}
//从链表中删去这两个结点
r[l[f[i]]]=r[f[i]];
l[r[f[i]]]=l[f[i]];
r[l[f[i-]]]=r[f[i-]];
l[r[f[i-]]]=l[f[i-]];
}
int cnt=;
for(int i=;i<=n;i+=){
printf("%d ",ans[i]);
if(++cnt>=) puts(""),cnt=;
}
puts("");
}
return ;
}
网上另外一种解法是对顶堆，所谓对顶堆，就是建立一个小根堆q1,大根堆q2,每次读入的数如果比中位数大，那么就把它放入小根堆中，反之放入大根堆中，小根堆元素必须等于大根堆或者是大根堆+1，如果不符合要求就调整，小根堆堆顶元素即是中位数
hdu和poj输出方式有点不一样
#include<bits/stdc++.h>
#define maxn 10005 using namespace std; priority_queue<int,vector<int>,greater<int> >q1;//小根堆，堆顶中位数
priority_queue<int,vector<int>,less<int> >q2;//、大根堆
int T,n,x,cnt,tot,ans[maxn]; void add(int x){
if(q1.empty()){
q1.push(x);
return;
}
if(x>q1.top()) q1.push(x);
else q2.push(x);
while(q1.size()<q2.size()){
q1.push(q2.top());
q2.pop();
}
while(q1.size()>q2.size()+){
q2.push(q1.top());
q1.pop();
}
} int main(){
scanf("%d",&T);
for(int tt=;tt<=T;tt++){
scanf("%d%d",&tt,&n);
printf("%d %d\n",tt,n/+);
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
cnt=tot=;
for(int i=;i<=n;i++){
scanf("%d",&x);
add(x);
if(i%!=) ans[tot++]=q1.top();
}
for(int i=;i<tot;i++){
if(i> && i%==) puts("");
if(i%) putchar(' ');
printf("%d",ans[i]);
}
puts("");
}
return ;
}