SP15376 RMID - Running Median 链表

解决本问题的主流算法都是对顶堆，在此提供一种 链表 的思路。 我们可以将所有数字读入、排序并插入到一个链表内，记排序后的数组为 $c$，那么现在的中位数在 $c$ 数组中的位置 $p = (n+1)/2$ 。 倒着处理每一个询问，问题转化为维护删除一个数后，中位数的位置 $p$ ，由于每次只会删除一个数，所以 $p$ 的位置只会变成 $pre[p]$，$nxt [p]$ 或 $p$，根据 $n$ 的奇偶性讨论即可。 最后，我们还需要知道原数组中的数在 $c$ 数组的位置，这个借用离散化的思想，二分查找一下即可。 下面贴 [POJ3784](http://poj.org/problem?id=3784) 的代码 ```cpp #include<iostream> #include<cstdio> #include<map> #include<algorithm> using namespace std; const int N=1002019; bool vis[N]; int n,p,js,a[N],pre[N],nxt[N],c[N],stk[N],id[N]; void del(int lc){ // 分类讨论 if(n&1 && lc>=p)p=pre[p]; if(!(n&1) && lc<=p)p=nxt[p]; pre[nxt[lc]]=pre[lc]; nxt[pre[lc]]=nxt[lc]; --n; } int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool check(int i){return !(i%10) && i;} int main() { int aq=read(); while(aq--){ int th=read(); n=read(); for(int i=1;i<=n;i++) a[i]=c[i]=read(),vis[i]=0; if(!(n&1))--n; sort(c+1,c+n+1); for(int i=1;i<=n;i++){ id[i]=lower_bound(c+1,c+n+1,a[i])-c; while(vis[id[i]])++id[i]; vis[id[i]]=1; // 上两行为查找原数在 c 数组中的位置 pre[i]=i-1,nxt[i]=i+1; } p=(n+1)>>1; int top=0; printf("%d %d\n",th,p); while(n){ stk[top++]=c[p]; if(n!=1)del(id[n]),del(id[n]); // 删数 else break; } reverse(stk,stk+top); for(int i=0;i<top;i++){ if(check(i))putchar('\n'); printf("%d",stk[i]); if(!check(i+1) && i!=top-1)putchar(' '); } putchar('\n'); } return 0; } ```