SP15376 RMID - Running Median 链表

· · 题解

解决本问题的主流算法都是对顶堆，在此提供一种 链表 的思路。

我们可以将所有数字读入、排序并插入到一个链表内，记排序后的数组为 c，那么现在的中位数在 c 数组中的位置 p = (n+1)/2 。

倒着处理每一个询问，问题转化为维护删除一个数后，中位数的位置 p ，由于每次只会删除一个数，所以 p 的位置只会变成 pre[p]，nxt [p] 或 p，根据 n 的奇偶性讨论即可。

最后，我们还需要知道原数组中的数在 c 数组的位置，这个借用离散化的思想，二分查找一下即可。

下面贴 POJ3784 的代码

#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;
}