链表(数组模拟)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=100010;
int n;
int l[N],r[N];
int p[N];//拿着未排序的序列的索引,去找其在双向链表的位置
PLI a[N],ans[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%ld",&a[i].first);
a[i].second=i;
}
sort(a+1,a+1+n);
a[0].first=1e11,a[n+1].first=1e11;//哨兵
//构建双向链表,p数组记录的是未排序序列在链表的位置;链表的元素序列是排序后的数组序列
for(int i=1;i<=n;i++){
p[a[i].second]=i;
l[i]=i-1,r[i]=i+1;
}
//因为要求的数是在左边,所以从后遍历,再删除当前节点,下面的i指未排序序列中第i个元素
for(int i=n;i>1;i--){
int index=p[i];//双向链表的位置
int left=l[index],right=r[index];
LL left_val=abs(a[index].first-a[left].first);
LL right_val=abs(a[index].first-a[right].first);
if(left_val<=right_val) ans[i]={left_val,a[left].second};
else ans[i]={right_val,a[right].second};
//删除该节点,右边节点的左指针等于左节点,左边节点的右指针等于右节点
l[right]=left,r[left]=right;
}
for(int i=2;i<=n;i++) printf("%ld %d\n",ans[i].first,ans[i].second);
return 0;
}
链表(结构体定义)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PII;
const int N=100010;
int n;
PII a[N],ans[N];
struct Node{
int idx;
LL val;
Node* pre,*next;
} head,tail;
Node* pos[N];//根据未排序索引(a[i].second)找到在双向链表的位置
//双链表新建节点,p的后面插入节点
Node* AddNode(Node* p,int idx){
Node* temp=new Node();
temp->idx=a[idx].second;
temp->val=a[idx].first;
temp->pre=p,temp->next=p->next;
p->next->pre=temp;
p->next=temp;
return temp;
}
void DeleteNode(Node* p){
p->pre->next=p->next;
p->next->pre=p->pre;
delete p;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%ld",&a[i].first);
a[i].second=i;
}
sort(a+1,a+n+1);
//初始化双向链表
head.val=1e11,tail.val=1e11;//另一种哨兵实现形式
head.next=&tail,tail.pre=&head;
//构建双向链表
for(int i=1;i<=n;i++){
pos[a[i].second]=AddNode(tail.pre,i);
}
//从后往前找邻近值
for(int i=n;i>1;i--){
LL lv=pos[i]->pre->val,rv=pos[i]->next->val,nv=pos[i]->val;
LL left=abs(lv-nv),right=abs(rv-nv);
if(left<=right) ans[i]={left,pos[i]->pre->idx};
else ans[i]={right,pos[i]->next->idx};
DeleteNode(pos[i]);
}
for(int i=2;i<=n;i++){
printf("%ld %d\n",ans[i].first,ans[i].second);
}
return 0;
}
TreeMap
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
int n=Integer.parseInt(br.readLine());
int[] arr=new int[n];
String[] str=br.readLine().split(" ");
for(int i=0;i<n;i++) arr[i]=Integer.parseInt(str[i]);
TreeMap<Integer,Integer> tree=new TreeMap<>();
tree.put(arr[0],1);
for(int i=1;i<n;i++){
Map.Entry<Integer,Integer> up=tree.ceilingEntry(arr[i]);
Map.Entry<Integer,Integer> down=tree.floorEntry(arr[i]);
int res=Integer.MAX_VALUE,pos=-1;
if(down!=null){
res=arr[i]-down.getKey();
pos=down.getValue();
}
if(up!=null && up.getKey()-arr[i]<res){
res=up.getKey()-arr[i];
pos=up.getValue();
}
pw.println(res+" "+pos);
pw.flush();
tree.put(arr[i],i+1);
}
pw.flush();
}
}