《算法竞赛进阶指南》1.3链表

136. 邻值查找

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求：

min 1≤j

以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj较小的那个。

输入格式

第一行输入整数n，代表序列长度。

第二行输入n个整数A1…An,代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共n-1行，每行输出两个整数，数值之间用空格隔开。

分别表示当i取2~n时，对应的min1≤j

数据范围

n≤10 ^5,|Ai|≤10 ^9

输入样例：

3

1 5 3

输出样例：

4 1

2 1

#include
#include
using namespace std;
typedef long long LL;
typedef pair PII; //数值 和下标
const int N = 100010;
int n;
int p[N], l[N], r[N]; //p[N]第n个点的位置，双向链表前驱后继
PII a[N], ans[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i].first;
a[i].secOnd= i;
}
sort(a + 1, a + 1 + n);

a[0].first = 1e9, a[n + 1].first = -1e9; //两个哨兵 不用处理边界 让开头和结尾 不影响结果
for(int i = 1; i <= n; i++) //从前往后遍历数组，建立链表
{
l[i] = i - 1, r[i] = i + 1;
p[a[i].second] = i; //记录每个点在双向链表的位置
}

for(int i = n; i > 1; i--)
{
int j = p[i], left = l[j], right = r[j];
int lv = abs(a[j].first - a[left].first);
int rv = abs(a[right].first - a[j].first);
if(lv <= rv) ans[i] = {lv, a[left].second};
else ans[i] = {rv, a[right].second}; //左右两边相等，选左边的数
// else ans[i] = {lv, min(a[left].second, a[right].second)};

r[left] = right, l[right] = left;
}

for(int i = 2; i <= n; i++)
cout < return 0;
}