【MX-J2-T4】Turtle and Cycles

形式化题目

给定环形排列 $a_0, \ldots, a_{n-1}$ 。一次操作：选 $i$ ，令 $a_i \leftarrow a_{i-1}+a_{i+1}-a_i$ （下标环回）。位置 $i$ 是"好的"当且仅当 $a_{i-1} < a_i$ 且 $a_{i+1} < a_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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/**
 * 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-08-14 15:01
 * update_at: 2026-08-14 16:40
 */
// brute.cpp：小数据暴力解，BFS 按题意直接模拟操作：
// 每次枚举位置 i 执行 a[i] <- a[i-1]+a[i+1]-a[i]，求到达
// "恰好一个好位置"状态的最少操作数。用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int n;
vector<int> a;

// 检查序列是否恰好存在一个"好位置"（峰）。
bool is_good(const vector<int>& v) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (v[(i - 1 + n) % n] < v[i] && v[(i + 1) % n] < v[i]) {
            cnt++;
            if (cnt > 1) return false;
        }
    }
    return cnt == 1;
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        a.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        if (is_good(a)) {
            cout << 0 << '\n';
            continue;
        }

        // BFS：状态是完整序列，操作是任一位置执行一次赋值
        map<vector<int>, int> dist;
        queue<vector<int>> q;
        dist[a] = 0;
        q.push(a);

        int ans = -1;
        while (!q.empty()) {
            vector<int> u = q.front();
            q.pop();
            int d = dist[u];
            for (int i = 0; i < n; i++) {
                vector<int> v = u;
                v[i] = v[(i - 1 + n) % n] + v[(i + 1) % n] - v[i];
                if (dist.count(v)) continue;
                if (is_good(v)) {
                    ans = d + 1;
                    break;
                }
                dist[v] = d + 1;
                q.push(v);
            }
            if (ans != -1) break;
        }
        cout << ans << '\n';
    }

    return 0;
}

brute.cpp 用 BFS 按题意直接模拟操作，直到出现恰好一个好位置的状态。它忠实于题意但状态指数爆炸，只适合 $n \leqslant 6$ 。

三步压缩把问题变成与数值无关的线性算法：

第一步，操作 = 交换相邻差分。设差分 $b_i = a_{i+1} - a_i$ （下标环回）。执行一次操作后可以验证：新 $b_{i-1}$ 等于旧 $b_i$ ，新 $b_i$ 等于旧 $b_{i-1}$ ，其余差分不动。所以一次操作就是在环上交换两个相邻差分，任意重排差分都可达。

第二步，好位置数 = 正差分段的个数。位置 $i$ 是峰 ⟺ $b_{i-1} > 0$ 且 $b_i < 0$ ，即差分符号序列中"正转负"的位置。环上每段连续正差分恰好贡献一个峰。

第三步，目标 = 正差分聚成一段。“恰好一个好位置” ⟺ 恰好一段正差分 ⟺ 环上所有正差分连续。设正差分有 $p$ 个，问题变成：把 $p$ 个位置在环上聚成连续 $p$ 个位置，最少相邻交换几次。

环上聚拢有标准公式：把正差分位置升序记 $pos_0 < \cdots < pos_{p-1}$ ，复制一份加 $n$ 得到长度 $2p$ 的序列；枚举聚段起点 $i$ （第 $i$ 个正差分作为段首），令 $x_k = pos_k - k$ （单调不减），子序列 $x_i \ldots x_{i+p-1}$ 的中位数 $med = x_{i + (p-1)/2}$ ，代价是

\sum_{k=i}^{i+p-1} |x_k - med|

用前缀和每个起点 $O(1)$ 求出，取所有 $i$ 的最小值。

下面这张表以样例 2（2 3 0 4 1，答案 1）展示差分符号的变化：

阶段	序列	差分符号	正差分段
初始	2 3 0 4 1	+ - + - +	3 段
操作 i=2	2 3 7 4 1	+ + - - +	2 段（环上第 4 与第 0 位相邻合并）

观察要点：一次操作交换了一对相邻差分，使符号从 + - + - + 变为 + + - - +，环上两个正差分块（位置 0、4 相邻）合并成一块，峰数从 2 降到 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/**
 * 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-08-14 15:01
 * update_at: 2026-08-14 16:40
 */
// P10843 【MX-J2-T4】Turtle and Cycles
// 操作 a[i] <- a[i-1]+a[i+1]-a[i] 等价于交换环上相邻差分 b[i-1] 与 b[i]。
// "好位置" = 差分符号序列中正差分段数 = 峰数；目标是恰好 1 个峰，
// 即把正差分在环上聚成一段，求最小相邻交换次数。
// 展开正差分位置 pos（升序、复制一份加 n），枚举聚段起点 i：
// 代价 = Σ|(pos[k]-k) - 中位数|，用前缀和 O(1) 求，取所有 i 的最小值。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
int a[MAXN];  // 环形排列

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 差分数组 b[i] = a[i+1] - a[i]（环形），正差分的位置
        vector<int> pos;
        for (int i = 0; i < n; i++) {
            if (a[(i + 1) % n] > a[i]) pos.push_back(i);
        }
        int p = (int)pos.size();
        if (p <= 1) {
            cout << 0 << '\n'; // 没有正差分段需要合并
            continue;
        }

        // 复制一份 pos + n，并把 x[j] = pos[j] - j 弄成单调不减
        vector<int> pos2(2 * p);
        for (int i = 0; i < p; i++) {
            pos2[i] = pos[i];
            pos2[i + p] = pos[i] + n;
        }
        vector<long long> x(2 * p), pref(2 * p + 1, 0);
        for (int i = 0; i < 2 * p; i++) {
            x[i] = pos2[i] - i;
            pref[i + 1] = pref[i] + x[i];
        }

        // 枚举聚段起点：正差分 pos[i..i+p-1] 聚成连续 p 个位置
        long long ans = LLONG_MAX;
        int mid_off = (p - 1) / 2; // 子序列中的中位数偏移
        for (int i = 0; i < p; i++) {
            int m = i + mid_off;      // 中位数的绝对下标
            long long med = x[m];     // 中位数
            // Σ_{k=i}^{i+p-1} |x[k] - med|：前缀和拆成左右两半
            long long left = (long long)(m - i + 1) * med - (pref[m + 1] - pref[i]);
            long long right = (pref[i + p] - pref[m + 1]) - (long long)(p - 1 - (m - i)) * med;
            ans = min(ans, left + right);
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度

时间：每组数据 $O(n)$ （正差分位置统计 + 前缀和 + 枚举起点）。
空间： $O(p)$ 。

总结

这道题的精髓是把"操作 + 目标"双双换成差分符号视角：操作变成环上相邻交换，目标变成正差分聚成一段，于是与具体数值完全无关，剩下一个环上聚拢问题，用中位数公式 $O(n)$ 解决。面对"改一个值"的怪异操作，先试差分化；面对"恰好一个峰"的目标，先想符号序列——这两步几乎总是开门的钥匙。环上聚拢类问题（如把一段标记聚成连续段的最小交换）都可迁移本解的"复制加 n + 中位数"套路。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22题意：操作 a[i] <- a[i-1]+a[i+1]-a[i]，目标恰好一个"好位置"
        |
        | 暴力：BFS 直接模拟（brute.cpp），状态爆炸
        v
关键观察 1：操作 = 环上交换相邻差分 b[i-1] 与 b[i]
        |
        v
关键观察 2：好位置 = 差分符号"正转负"处，峰数 = 正差分连续段数
        |
        v
关键观察 3：目标 = 环上所有正差分聚成连续一段
   问题与具体值无关，只剩 p 个正差分的位置
        |
        v
环上聚拢公式（main.cpp）
  pos 升序 + 复制加 n；枚举段首 i
  x[k] = pos[k] - k，中位数 med = x[i+(p-1)/2]
  代价 = Σ|x[k] - med|（前缀和 O(1)）
  取所有 i 的最小值
        |
        v
答案：最小相邻交换次数，复杂度 O(n)

图中主线是"差分化 → 符号化 → 聚拢化"。真正要掌握的是：怪异操作先找它在线性变换下的简单形态，目标再翻译成那个形态下的组合条件，两者对上后问题就降维了。

子任务编号	分值	$n \le$	$\sum n \le$	特殊性质	子任务依赖
$1$	$19$	$6$	$10^4$	无	无
$2$	$14$	$12$	$10^4$	无	$1$
$3$	$27$	$2 \cdot 10^3$	$10^4$	无	$1, 2$
$4$	$2$	$2 \cdot 10^5$	$2 \cdot 10^5$	$a_i = i$	无
$5$	$38$	$2 \cdot 10^5$	$2 \cdot 10^5$	无	$1, 2, 3, 4$