0x13 链表与邻接表

LB_tq · 2020-01-26 18:03:25 · 个人记录

邻值查找

链表先插入后删除的应用。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
struct node{
    int x;
    int b;
}a[maxn],ans[maxn];
int n,c[maxn],l[maxn],r[maxn];
int fr(){
    char ch;
    int sum,sign=1;
    while((ch=getchar())>'9'||ch<'0')
        if(ch=='-')
            sign=-1;
    sum=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        sum=(sum<<3)+(sum<<1)+ch-'0';
    return sign*sum;
}
bool cmp(node u,node v){
    return u.x<v.x;
}
int main(){
    n=fr();
    for(int i=1;i<=n;i++){
        a[i].x=fr();
        a[i].b=i;
        l[i]=i-1;
        r[i]=i+1;
    }
    l[1]=n;
    r[n]=1;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        c[a[i].b]=i;
    int u,v,y;
    for(int i=n;i>1;i--){
        y=c[i];
        u=abs(a[l[y]].x-a[y].x);
        v=abs(a[r[y]].x-a[y].x);
        if(u<v||(u==v&&a[l[y]].x<a[r[y]].x)){
            ans[i].x=u;
            ans[i].b=a[l[y]].b;
        }
        else{
            ans[i].x=v;
            ans[i].b=a[r[y]].b;
        }
        r[l[y]]=r[y];
        l[r[y]]=l[y];
    }
    for(int i=2;i<=n;i++)
        printf("%d %d\n",ans[i].x,ans[i].b);
    return 0;
}