传送门
牢骚
看到这种题，绝对的平衡树乱搞 但我需要练习链表啊 昨天偷懒贴了ldx的读优，结果他又没有加负数，气……
分析
将A数组排序后，建立链表 那么Ai在链表中的pre和nxt就分别对应其前驱和后继 从后往前查，查完后就删除这个点（因为题目要求是
1
<
=
j
<
i
1<=j<i
1<=j<i） 删除的话，就直接把 i 的nxt置为 i 这个点的前驱的nxt， i 的pre置为 i 这个点的后继的pre，这样就相当于把 i 跳过了 需要额外注意的就是序列与链表的一 一对应关系
代码
#include<bits/stdc++.h>
#define in read()
#define N 100009
using namespace std
;
inline int read(){
int f
=1,ans
=0;char ch
;
while((ch
=getchar())<'0'||ch
>'9') if(ch
=='-') f
=-1;
while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();
return f
==1?ans
:-ans
;
}
int n
,a
[N
];
struct node
{
int val
,id
;
int nxt
,pre
;
}p
[N
];
int tot
=0,b
[N
],idx
[N
];
int ans
[N
][3];
void remove(int pos
){
p
[p
[pos
].pre
].nxt
=p
[pos
].nxt
;
p
[p
[pos
].nxt
].pre
=p
[pos
].pre
;
}
bool cmp(const int &i
,const int &j
){
return a
[i
]<a
[j
];
}
int main(){
n
=in
;
int i
,j
,k
;
for(i
=1;i
<=n
;++i
) a
[i
]=in
,b
[i
]=i
;
sort(b
+1,b
+n
+1,cmp
);
tot
=1;
p
[1].val
=a
[b
[1]];
p
[1].id
=b
[1];
idx
[b
[1]]=1;
for(i
=2;i
<=n
;++i
){
idx
[b
[i
]]=++tot
;
p
[tot
].val
=a
[b
[i
]];p
[tot
].id
=b
[i
];
p
[tot
].pre
=tot
-1;p
[tot
-1].nxt
=tot
;
}
for(i
=n
;i
>=2;--i
){
int pos
=idx
[i
];
int mp
=2000000009,mn
=2000000009;
if(p
[pos
].pre
) mp
=abs(p
[pos
].val
-p
[p
[pos
].pre
].val
);
if(p
[pos
].nxt
) mn
=abs(p
[pos
].val
-p
[p
[pos
].nxt
].val
);
if(mp
<=mn
){
ans
[i
][0]=mp
;
ans
[i
][1]=p
[p
[pos
].pre
].id
;
}
else{
ans
[i
][0]=mn
;
ans
[i
][1]=p
[p
[pos
].nxt
].id
;
}
remove(pos
);
}
for(i
=2;i
<=n
;++i
) printf("%d %d\n",ans
[i
][0],ans
[i
][1]);
return 0;
}
