[JRKSJ R1] JFCA

题意

给定一个有 $n$ 个点的环，相邻点距离为 1。

每个点 $i$ 有两个属性 $a_i$ 和 $b_i$ 。
要求对每个点 $i$ ，找出满足：

$j \neq i$
$a_j \geqslant b_i$

的点 $j$ 中，和 $i$ 在环上的最短距离。

如果不存在这样的 $j$ ，输出 $-1$ 。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

int n;
int a[1005], b[1005];

int ring_distance(int x, int y) {
    int d = abs(x - y);
    return min(d, n - d);
}

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

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

    // brute.cpp：直接枚举每个 i 与所有 j，找满足 a[j] >= b[i] 的最小环距离。
    for (int i = 1; i <= n; i++) {
        int best = n + 1;
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                continue;
            }
            if (a[j] >= b[i]) {
                best = min(best, ring_distance(i, j));
            }
        }
        if (best == n + 1) {
            best = -1;
        }
        cout << best << (i == n ? '\n' : ' ');
    }

    return 0;
}

暴力做法就是对每个 $i$ 枚举所有 $j$ ，检查 $a_j \geqslant b_i$ ，然后更新最小环距离。复杂度是 $O(n^2)$ ，过不了 $10^5$ 。

这题的关键是把“满足 $a_j \geqslant b_i$ 的点”看成一个按阈值变化的集合。

如果我们把所有点按 $a_j$ 从大到小排序，再把所有询问点按 $b_i$ 从大到小排序，那么在处理某个 $b_i$ 时：

所有 $a_j \geqslant b_i$ 的点都应该已经加入集合
所有 $a_j < b_i$ 的点都还没加入集合

于是问题就变成：

在一个环上，给定若干个“活跃位置”，求某个位置到最近活跃位置的距离。

我们用一个有序集合 set<int> 维护当前所有活跃位置。
对于位置 $i$ ，离它最近的活跃点只可能是：

在有序集合里紧靠它右边的点
紧靠它左边的点
以及考虑环形首尾相连后，集合里的最小点和最大点

检查这几个候选位置，取最小环距离即可。

注意还要排除 $j = i$ 的情况：如果集合里只有自己一个点，答案应为 $-1$ ；如果最近位置恰好等于自己，就继续看前驱/后继。

整个过程是典型的离线排序 + 有序集合维护。

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct NodeA {
    int value;
    int pos;
};

struct NodeB {
    int value;
    int pos;
};

int n;
int a[MAXN], b[MAXN];
int answer[MAXN];
NodeA arr_a[MAXN];
NodeB arr_b[MAXN];

int ring_distance(int x, int y) {
    int d = abs(x - y);
    return min(d, n - d);
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        arr_a[i].value = a[i];
        arr_a[i].pos = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        arr_b[i].value = b[i];
        arr_b[i].pos = i;
    }

    sort(arr_a + 1, arr_a + n + 1, [](const NodeA &x, const NodeA &y) {
        return x.value > y.value;
    });
    sort(arr_b + 1, arr_b + n + 1, [](const NodeB &x, const NodeB &y) {
        return x.value > y.value;
    });

    set<int> pos_set;
    int p = 1;

    for (int i = 1; i <= n; i++) {
        while (p <= n && arr_a[p].value >= arr_b[i].value) {
            pos_set.insert(arr_a[p].pos);
            p++;
        }

        int x = arr_b[i].pos;
        if (pos_set.empty() || (int)pos_set.size() == 1 && *pos_set.begin() == x) {
            answer[x] = -1;
            continue;
        }

        int best = n + 1;
        set<int>::iterator it = pos_set.lower_bound(x);

        if (it != pos_set.end()) {
            if (*it != x) {
                best = min(best, ring_distance(x, *it));
            }
            else {
                set<int>::iterator nx = it;
                nx++;
                if (nx != pos_set.end()) {
                    best = min(best, ring_distance(x, *nx));
                }
            }
        }
        if (it != pos_set.begin()) {
            set<int>::iterator pre = it;
            pre--;
            best = min(best, ring_distance(x, *pre));
        }

        int first_pos = *pos_set.begin();
        int last_pos = *pos_set.rbegin();
        if (first_pos != x) {
            best = min(best, ring_distance(x, first_pos));
        }
        if (last_pos != x) {
            best = min(best, ring_distance(x, last_pos));
        }

        answer[x] = best;
    }

    for (int i = 1; i <= n; i++) {
        cout << answer[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}

复杂度

排序复杂度： $O(n log n)$
每个点插入集合一次、查询一次： $O(n log n)$

总时间复杂度是 $O(n log n)$ ，空间复杂度是 $O(n)$ 。

总结

这题的核心不是环，而是先看出“ $a_j \geqslant b_i$ 可以按阈值离线处理”。

离线之后，环上的最近点查询只需要在有序集合里看前驱后继，再补上首尾跨环情况即可。

目录

题意

思路

代码

复杂度

总结