Python3 解法, 执行用时: 1331ms, 内存消耗: 21504K, 提交时间: 2023-07-22 15:37:24

from bisect import bisect_left
n=int(input())
arr=list(map(int,input().split()))
sortlist=[arr[0]]
dic={}
for i,it in enumerate(arr): dic[it]=i 
res=[]
for it in arr[1:]:
    ind=bisect_left(sortlist, it)
    sortlist.insert(ind, it)
    if ind==0:
        print(abs(it-sortlist[1]),dic[sortlist[1]]+1)
    elif ind==len(sortlist)-1:
        print(abs(it-sortlist[-2]),dic[sortlist[-2]]+1)
    else:
        if abs(it-sortlist[ind-1])<=abs(it-sortlist[ind+1]):
            print(abs(it-sortlist[ind-1]),dic[sortlist[ind-1]]+1)
        else:
            print(abs(it-sortlist[ind+1]),dic[sortlist[ind+1]]+1)
         

C++(g++ 7.5.0) 解法, 执行用时: 60ms, 内存消耗: 8484K, 提交时间: 2023-07-26 15:35:38

#include<bits/stdc++.h>
using namespace std;
long long a[1000001];
set<pair<long long,long long> >st;
int main(){
	long long n,ans1,ans2;scanf("%lld",&n);
	for(register int i=1;i<=n;++i){
		scanf("%lld",&a[i]);ans1=1e18;
		if(i==1)st.insert(make_pair(a[i],i));
		else{
			st.insert(make_pair(a[i],i));
			set<pair<long long,long long> >::iterator it=st.lower_bound(make_pair(a[i],i));
			if(++it!=st.end())ans1=it->first-a[i],ans2=it->second;
			--it;
			if(it--!=st.begin()&&ans1>=a[i]-it->first)ans1=a[i]-it->first,ans2=it->second;
			printf("%lld %lld\n",ans1,ans2);
		}
	}
}

C++ 解法, 执行用时: 188ms, 内存消耗: 7668K, 提交时间: 2021-09-01 21:06:44

#include "bits/stdc++.h"
using namespace std;
set<pair<long long,int>> q;
long long a,n;
int main()
{
	q.insert({-9999999999999999,-1});
    q.insert({9999999999999999,-1});
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		if(i!=1)
		{
			auto j=q.upper_bound({a,i});
			auto jj=j--;
			if(a-j->first<=jj->first-a) cout<<a-j->first<<' '<<j->second<<endl;
			else cout<<jj->first-a<<' '<<jj->second<<endl; 
		}
		q.insert({a,i});
	}
}