【MX-J2-T1】Turtle and Sequences

形式化题目

给定长度 $n$ 的序列 $a_1, \ldots, a_n$ 。每次操作：若存在相邻两个元素不同，删除右元素，并把左元素改为任意整数。求最多能操作多少次。

思路

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

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/**
 * 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 15:20
 */
// brute.cpp：小数据暴力解，直接模拟操作过程：
// 反复寻找相邻不同的位置，删除右元素并把左元素改成"全新值"（当前最大值+1），
// 直到无法操作，统计操作次数。用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a; // 当前序列

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

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

    int ans = 0;
    while (true) {
        // 找第一处相邻不同的位置
        int pos = -1;
        for (int i = 0; i + 1 < (int)a.size(); i++) {
            if (a[i] != a[i + 1]) {
                pos = i;
                break;
            }
        }
        if (pos == -1) break; // 没有相邻不同，无法操作

        // 找当前最大值，构造一个与所有元素都不同的新值
        long long mx = 0;
        for (long long x : a) mx = max(mx, x);

        // 删除 a[pos+1]，把 a[pos] 改成全新值
        a[pos] = mx + 1;
        a.erase(a.begin() + pos + 1);
        ans++;
    }

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

brute.cpp 直接模拟操作过程：每轮找第一处相邻不同，删除右元素，把左元素改成"当前最大值 + 1"（一个全新值），计数直到无法操作。它与题意一一对应，但每轮要 $O(m)$ 找位置、 $O(m)$ 删除，总 $O(n^2)$ ，无法通过 $10^5$ 的数据。

两条关键观察直接给出答案：

每次操作删一个元素，序列长度从 $n$ 减到 1，任何策略最多 $n-1$ 次；
只要序列不全相同，就总能继续操作：不全相同 ⟺ 存在相邻不同；而且把 $a_i$ 改成"全新值"（比如当前最大值 $+1$ ）后，它与左右邻居都不同，操作后序列仍不全相同（长度 $\geqslant 2$ 时），可以一直删下去。

所以答案只由"序列是否全相同"决定：

全相同：一次都动不了，答案是 $0$ ；
否则：可以一直删到只剩一个元素，答案是 $n-1$ 。

下面这张表展示样例 3（1 1 45 14）用"改全新值"策略的完整操作过程：

操作	操作前序列	选中的相邻不同	操作后序列	次数
1	1 1 45 14	(1, 45) 位置 2	1 46 14	1
2	1 46 14	(1, 46) 位置 1	47 14	2
3	47 14	(47, 14) 位置 1	48	3

观察要点：每一步把左元素改成全新值（45→46 处原值 45 被删，左元素 1 变 46；46→47 同理），新值与邻居必然不同，因此每轮都能找到下一个相邻不同位置，直到序列只剩一个元素，恰好达到上界 $n-1 = 3$ 。

代码

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/**
 * 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 15:20
 */
// P10840 【MX-J2-T1】Turtle and Sequences
// 每次操作删除一个元素，上界 n-1 次。
// 若序列不是全相同，总能通过把 a_i 改成全新值继续操作，答案为 n-1；
// 若全相同则无法开始，答案为 0。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long a[MAXN]; // 输入序列

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

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

    // 判断是否所有元素相等
    bool all_same = true;
    for (int i = 2; i <= n; i++) {
        if (a[i] != a[1]) {
            all_same = false;
            break;
        }
    }

    cout << (all_same ? 0 : n - 1) << '\n';
    return 0;
}

复杂度

时间：一遍扫描判断是否全相同， $O(n)$ 。
空间： $O(n)$ 存序列。

总结

这道题的思维含量在于把"能操作几次"还原为两个简单事实：长度每步减 1 给出硬上界 $n-1$ ；"改任意整数"提供无限续命手段，只要初始不全相同就能一直删到底。于是 $O(n^2)$ 的模拟可以压缩成一次 $O(n)$ 扫描。“操作允许任意改值"这类自由度往往是解题钥匙——它把"能否持续"变成"初始状态是否已坏”。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18题意：相邻不同 → 删右元素，左元素改成任意整数
        |
        | 每操作一次，长度减 1
        v
上界：最多 n-1 次（删到只剩 1 个元素）
        |
        | 关键：不全相同 ⟺ 存在相邻不同
        v
续命手段：把 a[i] 改成全新值（最大值+1）
   与左右邻居都不同 → 操作后仍不全相同 → 可继续删
        |
        v
答案：
  全相同    → 0
  不全相同  → n-1（总能删到只剩 1 个）
        |
        v
实现：一遍扫描判断全相同，O(n)

图中主线是"上界（长度）→ 可达性（新值续命）→ 二分支答案"。真正要抓住的是：操作的自由度（任意改值）使问题从"策略选择"退化为"初始状态判定"。

子任务编号	分值	$n \le$	特殊性质	子任务依赖
$1$	$34$	$2$	无	无
$2$	$19$	$10^5$	$a_1 = a_2 = \cdots = a_n$	无
$3$	$47$	$10^5$	无	$1, 2$