形式化题目

给定互不相同的整数 $A_1, A_2, \dots, A_n$。对每个 $i \in [2, n]$，记前缀集合 $S_i = \{A_1, \dots, A_{i-1}\}$，求

以及取到这个最小值的下标 $P_i$。若最小值点不唯一（左右两侧距离相等），则选使 $A_j$ 较小的那个 $j$。

其中 $n \leqslant 10^5$，$|A_i| \leqslant 10^9$，序列中的数两两不同。

一个例子：$A = (1, 5, 3)$，则 $S_2 = \{1\}$ 给出 $D_2 = 4, P_2 = 1$；$S_3 = \{1, 5\}$ 中 $|3-1| = |3-5| = 2$ 打成平手，按规则取 $A_j$ 较小的 $A_1$，得 $D_3 = 2, P_3 = 1$。

正解

思路

朴素做法与瓶颈。 直接翻译题意：对每个 $i$，把 $A_1 \dots A_{i-1}$ 全扫一遍取最小差值。这是 $O(n^2)$，$n = 10^5$ 时约 $5 \times 10^9$ 次内层操作，必然超时。瓶颈不是「比较」这个动作，而是比较的对象太多——前缀里绝大多数元素根本不可能成为答案，必须找到一个「只留常数个候选」的刻画。

关键观察一：答案只需看左右邻居。

设 $S_i$ 排序后形如 $x_1 < x_2 < \dots < x_m$，并令

（不存在时视作 $\pm\infty$）。那么对任意 $x \in S_i$：若 $x \leqslant l$，有 $|A_i - x| = A_i - x \geqslant A_i - l = |A_i - l|$；若 $x \geqslant r$，有 $|A_i - x| = x - A_i \geqslant r - A_i = |A_i - r|$。$S_i$ 被 $A_i$ 分成这两部分，所以

最小值一定在 $A_i$ 的两个有序邻居中取到，其余元素一律不用看。于是问题变成：维护一个有序集合，支持「插入一个数」和「查某个数的前驱/后继」。

关键观察二：把插入倒过来变成删除。

在 C++ 里这个有序集合就是 std::set（平衡树），$O(n \log n)$ 直接解决。但 Python 标准库没有平衡树：bisect.insort 往 list 里插入是 $O(n)$ 的搬移，整体会退化成 $O(n^2)$。

换一个方向看时间轴。正向第 $i$ 步查询的集合是 $S_i = \{A_1, \dots, A_{i-1}\}$；如果令 $T = \operatorname{sort}(A)$ 是全体元素的有序表，那么

也就是「从全集中挖掉 $A_i$ 及其后面所有元素」。于是从 $i = n$ 倒着处理：一开始有序表里放着全部 $n$ 个数；处理到第 $i$ 步时，$A_{i+1}, \dots, A_n$ 已经在前面几步被挖掉了，表里剩下 $S_i \cup \{A_i\}$。而 $A_i$ 自己在表里的位置正是它的左右邻居夹着的那个空档，「查邻居」和「删自己」可以在同一步完成。

这一步把「插入」换成了「删除」，而删除在有序表上是很便宜的操作——前提是用对结构。

关键观察三：有序表用双向链表实现。

在有序表上删掉一个元素，只需让它左边一格指向右边一格、右边一格指向左边一格，$O(1)$，不必搬移任何元素。链表节点用「在有序表里的位置」编号 $0 \dots n-1$：

一步操作就是下面四件事：

比较键为什么写成三元组？因为题面的规则是「差值最小；差值相同时取 $A_j$ 较小的那个」，而这两个条件恰好就是 $(|A_i - A_j|, A_j)$ 的字典序；再补上原始下标 $j$ 作为第三关键字，可以让比较键成为全序，代码不必再写任何平局分支。

推演一：样例 1 5 3。 排序后有序表是 $1, 3, 5$（下标 $1, 3, 2$），倒序从 $i = 3$ 开始：

最终按 $i = 2, 3$ 的顺序输出 4 1 与 2 1，与题面样例一致。第 1 步正是平局：差值都是 2，三元组比较的第二位把 $A_j$ 较小的下标 1 选了出来。

推演二：10 3 7 8 2（即 $A_1=10, A_2=3, A_3=7, A_4=8, A_5=2$）。 排序后有序表为 $2, 3, 7, 8, 10$（下标 $5, 2, 3, 4, 1$），每行是一次倒推，候选写成三元组 $\bigl(|A_i - A_j|,\ A_j,\ j\bigr)$：

读者可重点看第 2 步：$A_4 = 8$ 的左邻居是 $A_3 = 7$（差值 $1$）、右邻居是 $A_1 = 10$（差值 $2$），取小者得 1 3。第 3 步则是差值不等但都为正的常规情形。倒序算出的这四行答案按 $i = 2, 3, 4, 5$ 重新排列，正好是程序输出的 7 1、3 1、1 3、1 2。

综上所述，算法是：

1. 排序得到有序表，建立 order / rank / prev / nxt；
2. $i$ 从 $n$ 递减到 $2$：取 prev[rank[i]] 与 nxt[rank[i]] 两个候选，比较后写答案，再把 rank[i] 从链表里摘掉；
3. 把答案按 $i = 2 \dots n$ 的顺序输出。

代码

main.py 里的变量名与上文一一对应：order 和 rank 合起来表示有序表，prev / nxt 是双向链表，ans 是按原下标预分配的输出槽位——倒序算出的答案写进 ans[i]，最后一次性 '\n'.join(ans[1:]) 输出。prev = list(range(-1, n - 1)) 与 nxt = list(range(1, n + 1)) 再补一个 nxt[n - 1] = -1，就得到两端为哨兵的双向链表；min((abs(...), a[order[l]], order[l]) for l in (prev[k], nxt[k]) if l >= 0) 一行同时完成「过滤哨兵」「比差值」「平局取较小 $A_j$」三件事。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:28
# update_at: 2026-10-01 11:28

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n: int = next(data)
    a: list[int] = [next(data) for _ in range(n)]

    # 有序表：order 是按数值升序排好的原始下标，rank[i] 是下标 i 在表里的位置。
    order: list[int] = sorted(range(n), key=a.__getitem__)
    rank: list[int] = [0] * n
    for k, i in enumerate(order):
        rank[i] = k

    # 双向链表：在有序表上删掉一个数只改两条边，不需要搬移元素。
    prev: list[int] = list(range(-1, n - 1))  # prev[k] = k-1，-1 表示没有前驱
    nxt: list[int] = list(range(1, n + 1))    # nxt[k] = k+1
    nxt[n - 1] = -1                           # 末尾哨兵：最后一个位置没有后继

    ans: list[str] = [""] * n
    for i in range(n - 1, 0, -1):
        k = rank[i]
        # 只需比较有序表上的前驱与后继：任何更远的数，差值都不会更小。
        # 三元组按字典序比较，正好先比差值，再比 A_j 较小者，最后比下标。
        diff, value, pos = min(
            (abs(a[order[l]] - a[i]), a[order[l]], order[l])
            for l in (prev[k], nxt[k])
            if l >= 0
        )
        ans[i] = f"{diff} {pos + 1}"  # 题面要求输出 1 起始的下标

        if prev[k] >= 0:
            nxt[prev[k]] = nxt[k]  # 摘掉 i 之后，左右邻居直接相连
        if nxt[k] >= 0:
            prev[nxt[k]] = prev[k]

    # 倒序算出的答案按 (i = 2..n) 的下标顺序输出，n = 1 时没有任何一行
    sys.stdout.write('\n'.join(ans[1:]) + ('\n' if n > 1 else ''))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:25
 * update_at: 2026-10-06 15:25
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // n <= 1e5

int n;
ll a[MAXN];   // a[1..n]：原序列，数值两两不同
int order[MAXN]; // order[k]：有序表第 k 个位置上放的是原序列的哪个下标
int rank_of[MAXN]; // rank_of[i]：A_i 在有序表里的位置
int pre[MAXN]; // pre[k]：有序表里位置 k 的前一个位置，0 表示无前驱
int nxt[MAXN]; // nxt[k]：有序表里位置 k 的后一个位置，0 表示无后继
ll ans_diff[MAXN]; // ans_diff[i]：第 i 个数的最近差值
int ans_pos[MAXN]; // ans_pos[i]：取到最近差值的原始下标

// 按数值升序排列原始下标，供 sort 使用
bool cmp_value(int x, int y) {
    return a[x] < a[y];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        order[i] = i;
    }

    // 排序得到有序表，并记录每个下标在表中的位置
    sort(order + 1, order + n + 1, cmp_value);
    for (int k = 1; k <= n; k++) {
        rank_of[order[k]] = k;
    }

    // 建双向链表，删除一个位置只需改两条边
    for (int k = 1; k <= n; k++) {
        pre[k] = k - 1;
        nxt[k] = k + 1;
    }
    pre[1] = 0;
    nxt[n] = 0;

    // 从 i=n 倒推：此时表里是 S_i 并上 A_i，取它的左右邻居即为候选
    for (int i = n; i >= 2; i--) {
        int k = rank_of[i];
        ll best_diff = -1;
        ll best_val = 0;
        int best_pos = 0;
        for (int t = 0; t < 2; t++) {
            int p = (t == 0 ? pre[k] : nxt[k]);
            if (p == 0) continue;
            int j = order[p];
            ll diff = a[i] - a[j];
            if (diff < 0) diff = -diff;
            // 三元组 (差值, A_j, 下标) 字典序最小者
            bool better = false;
            if (best_diff == -1) better = true;
            else if (diff < best_diff) better = true;
            else if (diff == best_diff && a[j] < best_val) better = true;
            else if (diff == best_diff && a[j] == best_val && j < best_pos) better = true;
            if (better) {
                best_diff = diff;
                best_val = a[j];
                best_pos = j;
            }
        }
        ans_diff[i] = best_diff;
        ans_pos[i] = best_pos;

        // 摘掉 A_i：它的左右邻居直接相连
        if (pre[k] != 0) nxt[pre[k]] = nxt[k];
        if (nxt[k] != 0) pre[nxt[k]] = pre[k];
    }

    for (int i = 2; i <= n; i++) {
        printf("%lld %d\n", ans_diff[i], ans_pos[i]);
    }
    return 0;
}

复杂度

• 时间复杂度：$O(n \log n)$。排序是唯一的超线性步骤（sorted 由 C 实现）；建表 $O(n)$，倒序 $n-1$ 步里每步只做常数次下标访问和比较，删除只改两条边，$O(1)$。
• 空间复杂度：$O(n)$。a、order、rank、prev、nxt、ans 各占 $O(n)$ 个 Python 对象。
• 与 C++ 正解（std::set + lower_bound，或先建有序表再倒删的链表写法）同阶，瓶颈都是排序。实测最大用例 $n = 10^5$ 约 0.08 s、峰值内存约 50 MB，相对 1000 ms / 128 MB 余量充足。

总结

• 朴素做法 $O(n^2)$ 的瓶颈在于比较对象太多；先证明答案只可能来自有序邻居，就能把候选压到常数个。
• 证明的写法是两侧夹逼：$A_i$ 左边越远越小、右边越远越大，所以极值必在紧邻的两个数上取得。
• 时间轴反转是关键一步：正向需要「插入」而 Python 的 list 插入是 $O(n)$；把 $S_i$ 看成「全集中挖掉 $A_i$ 及之后所有元素」，就能改成从 $n$ 倒推的「删除」，每步 $O(1)$。
• 有序表用双向链表表达：删除只改两条边；节点编号用有序表位置，rank 提供从原下标到位置的映射。
• 平局规则不必写分支，把候选编码成 $(|A_i - A_j|, A_j)$ 的字典序比较即可。

图示解析

下面这张 ASCII 路线图串起从朴素做法到最终做法的三步降复杂度：

1
2
3
4
5
6
7
8
9题意：对每个 i，在 {A_1..A_{i-1}} 中找最近的数
`- 朴素：每个 i 扫完前缀                        O(n^2)
   `- 瓶颈：候选太多，前缀里绝大多数数不可能成为答案
      `- 观察一：答案只在有序邻居 l < A_i < r 中取到    （两侧夹逼）
         `- 问题变成：维护有序集合，支持 插入 + 查前驱/后继
            `- 观察二：S_i = 全集 挖掉 {A_i..A_n}
               `- 从 i=n 倒推：查询 + 删除，都是 O(1) 的局部操作
                  `- 观察三：有序表用双向链表表示，删除只改两条边
                     `- 排序 O(n log n) + 线性倒推 = 总复杂度 O(n log n)

先看每一层解决了什么：第一层把 $O(n^2)$ 个候选换成 2 个；第二层把「插入」换成「删除」，绕开 Python 没有平衡树的问题；第三层给有序表配上 $O(1)$ 删除的实现。顺着 `- 的分支往下读，每一步都只依赖上一层已经证明的结论，最后的总复杂度由排序决定。