CH1301邻值查找 – 老虫儿的笔记本

撰写 Lao Chonger 于 2019年3月13日 2019年3月13日链表

描述

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 A_i，求：
min(1≤j<i) ⁡|A_i-A_j|
以及令上式取到最小值的 j（记为 P_i）。若最小值点不唯一，则选择使 A_j 较小的那个。

输入格式

第一行一个整数n，第二行n个数A_1~A_n。

输出格式

n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的 min(1≤j<i) ⁡|A_i-A_j| 和 P_i 的值。

样例输入

3
1 5 3

样例输出

4 1
2 1

数据范围与约定

对于30%的数据: n<=100
对于70%的数据: n<=10^4
对于100%的数据: n<=10^5, |A_i|<=10^9

题解：

链表，倒序，前驱后继


#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
const int maxn=1e5+10;
struct node {
	int x,id;
}a[maxn];
bool cmp(node n1,node n2) {
	return n1.x<n2.x;
}
int List[maxn];
int pre[maxn],nextt[maxn];
int ans[maxn],ans_j[maxn];
int main() {
	int n;
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i].x), a[i].id=i;
	sort(a+1,a+n+1,cmp);
	
	for(int i=1; i<=n; i++){
		List[a[i].id]=i;
		pre[i]=i-1;
		nextt[i]=i+1;
	}
	
	for(int i=n; i>=2; i--) {
		int t=List[i];
		ans[i]=INF;
		if(pre[t]!=0) {//有前驱
			int d=abs(a[t].x-a[pre[t]].x);
			if(d<ans[i]){
				ans[i]=d;
				ans_j[i]=a[pre[t]].id;
			} 
		}
		if(nextt[t]!=n+1) {//有后继 
			int d=abs(a[t].x-a[nextt[t]].x);
			if(d<ans[i]){
				ans[i]=d;
				ans_j[i]=a[nextt[t]].id;
			}
		}
		nextt[pre[t]]=nextt[t];
		pre[nextt[t]]=pre[t];
	}

	rep(i,2,n)printf("%d %d\n",ans[i],ans_j[i]);
	return 0;
}

发表评论取消回复