链表

将元素用一条链串起来，删除和修改操作均为O(1)，查询操作为O(n)

实现

#include <bits/stdc++.h>
using namespace std;

int Data[20005],Next[20005];
  //数据        下一个的下标
int main(){
  int num,cnt,n,m,now,pre,tmp;
  cin>>n>>m>>num;
  for (int i=1;i<=n;++i){ //初始化
    Data[i]=i;
    Next[i]=i+1;
  }
  Next[n]=1;
  now=n;
  cnt=0;
  for (int i=1;i<=m;++i){
    cnt=0;
    while (cnt<num){    //计数操作
      cnt++;
      pre=now;
      now=Next[now];
    }
    printf("%d\n",Data[now]);
    tmp=now;            //删除操作
    Next[pre]=Next[now];
    while (cnt<2*num){
      cnt++;
      pre=now;
      now=Next[now];
    }
    Next[tmp]=Next[now];//插入操作
    Next[now]=tmp;
    now=Next[now];
  }
  return 0;
}

应用

邻值查找

进阶指南P59
一种思路是用STL set
这里可以采用离线做法，先读入后全部排序，并记录原始元素的位置，并建立链表，之后不断进行删除操作

#include <bits/stdc++.h>
using namespace std;

struct node{
    int id,v;
}t[100005];

bool cmp(node x,node y){
    return x.v<y.v;
}

int a[100005],id[100005],Next[100005],Pre[100005],V[100005],n;

stack <node> st;

node get(int id){
    node ans{0,0x7fffffff};
    if (Pre[id]!=0){
        int tmp=abs(V[Pre[id]]-V[id]);
        if (tmp<ans.v) ans.v=tmp,ans.id=t[Pre[id]].id;
    }
    if (Next[id]!=n+1){
        int tmp=abs(V[Next[id]]-V[id]);
        if (tmp<ans.v) ans.v=tmp,ans.id=t[Next[id]].id;
    }
    return ans;
}

void del(int id){
    int p=Pre[id],n=Next[id];
    Next[p]=n;
    Pre[n]=p;
}

void pr(){
    for (int i=0;i!=n+1;i=Next[i]) printf("%d ",V[i]);
        puts("");
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]),t[i].id=i,t[i].v=a[i];
    sort(t+1,t+n+1,cmp);
    for (int i=1;i<=n;++i) id[t[i].id]=i;
    for (int i=1;i<=n;++i){
        Next[i]=i+1;
        Pre[i]=i-1;
        V[i]=t[i].v;
    }
    Next[0]=1;
    Pre[n+1]=n;
    for (int i=n;i>=2;--i){
        st.push(get(id[i]));
        del(id[i]);
    }
    while (!st.empty()) printf("%d %d\n",st.top().v,st.top().id),st.pop();
    return 0;
}

动态中位数

这题可以使用对顶堆的做法，见：
[post cid=”57” /]
这里也可以采用离线做法，先排序，记录原始元素在链表中的位置，然后逐个删除，判断当前中位数两边的元素个数之差，然后调整即可
代码见 进阶指南P59

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/27/