Range Reconstruction

题意

给定一个数组所有区间的全距：

text

1r[i][j] = max(a[i..j]) - min(a[i..j])

要求构造任意一个数组，使得它的所有区间全距都和输入一致。

思路

先看小数据暴力：相邻两数的差的绝对值已经确定，枚举每个相邻差值的正负号，生成完整数组后检查。

cpp

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/**
 * 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-07-11 21:22
 * update_at: 2026-07-11 21:24
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
long long r[MAXN][MAXN];
long long a[MAXN];
bool found;

bool check_all() {
    for (int i = 1; i <= n; i++) {
        long long mn = a[i];
        long long mx = a[i];
        for (int j = i; j <= n; j++) {
            if (mn > a[j]) mn = a[j];
            if (mx < a[j]) mx = a[j];
            if (mx - mn != r[i][j]) {
                return false;
            }
        }
    }
    return true;
}

// 枚举相邻两数差值的正负号，生成完整数组后统一检查。
void dfs_build(int pos) {
    if (found) return;

    if (pos == n + 1) {
        if (check_all()) {
            found = true;
        }
        return;
    }

    long long d = r[pos - 1][pos];
    a[pos] = a[pos - 1] + d;
    dfs_build(pos + 1);
    if (found) return;

    a[pos] = a[pos - 1] - d;
    dfs_build(pos + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            cin >> r[i][j];
        }
    }

    a[1] = 0;
    dfs_build(2);

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

暴力的枚举对象是：

text

1
2
3a[i] = a[i-1] + r[i-1][i]
或
a[i] = a[i-1] - r[i-1][i]

共有 $2^{N-1}$ 种，不能直接做。

正解从右往左构造。先令：

text

1a[N] = 0

假设 a[i+1..N] 已经构造好。因为：

text

1r[i][i+1] = |a[i] - a[i+1]|

所以 a[i] 只有两种可能：

text

1
2a[i] = a[i+1] + r[i][i+1]
a[i] = a[i+1] - r[i][i+1]

加入 a[i] 后，右侧旧区间都不变。新增的约束只来自：

text

1[i,i], [i,i+1], ..., [i,N]

所以先尝试第一种，如果所有以 i 为左端点的区间全距都正确，就保留；否则改成第二种。输入保证有解，因此两种方向中至少一种可行。

注意：本题输出不唯一。整体平移或整体取反都不会改变区间全距，所以你的输出不需要和样例完全一样，只要合法即可。

代码

cpp

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/**
 * 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-07-11 21:22
 * update_at: 2026-07-11 21:24
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

int n;
long long r[MAXN][MAXN];
long long ans[MAXN];

bool check_prefix(int left) {
    long long mn = ans[left];
    long long mx = ans[left];

    for (int j = left; j <= n; j++) {
        if (mn > ans[j]) mn = ans[j];
        if (mx < ans[j]) mx = ans[j];
        if (mx - mn != r[left][j]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            cin >> r[i][j];
        }
    }

    ans[n] = 0;
    for (int i = n - 1; i >= 1; i--) {
        ans[i] = ans[i + 1] + r[i][i + 1];
        if (!check_prefix(i)) {
            ans[i] = ans[i + 1] - r[i][i + 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

复杂度

每个左端点检查一遍右端点，总时间复杂度为 $O(N^2)$ 。

存储区间全距矩阵需要 $O(N^2)$ 空间。

总结

本题的关键是不要试图恢复原数组本身，而是恢复一个全距相同的数组。

从右往左构造时，每个新数只有正负两个候选；检查新增左端点区间即可把指数枚举降到 $O(N^2)$ 。

目录

题意

思路

代码

复杂度

总结