P1152 欢乐的跳

题目描述

一个 \(n\) 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 \([1,n-1]\) 之间的所有整数，则称之符合“欢乐的跳”，如数组 \(\{1,4,2,3\}\) 符合“欢乐的跳”，因为差的绝对值分别为：\(3,2,1\)。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数 \(n(1 \le n \le 1000)\) 开始，接下来 \(n\) 个空格隔开的在 \([-10^8,10^8]\) 之间的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。

输入输出样例 #1

输入 #1

4 1 4 2 3

输出 #1

Jolly

输入输出样例 #2

输入 #2

5 1 4 2 -1 6

输出 #2

Not jolly

说明/提示

\(1 \le n \le 1000\)

Tip

b站讲解视频

好，这题其实不推荐用快排，但你既然想练“排序思路”，我就给你一版排序解法（用快排实现）👇

📌 题目分析

👉 本质： 判断差值集合是否等于：

{1, 2, ..., n-1}

👉 类型： 排序 + 判定

🧠 解题思路（快排版）

1️⃣ 核心建模

先构造差值数组：

d[i] = |a[i] - a[i-1]|   (i = 1 ~ n-1)

得到一个长度为 n-1 的数组 d

2️⃣ 排序思想

👉 如果是“欢乐的跳”，那么排序后应该是：

1, 2, 3, ..., n-1

3️⃣ 算法流程

Step 1：计算差值数组

d[i] = abs(a[i] - a[i-1]);

Step 2：用快排排序 d

quick_sort(d, 0, n-2);

Step 3：检查是否合法

d[0] == 1
d[1] == 2
...
d[n-2] == n-1

只要有一个不满足 → ❌

4️⃣ 对比标记法

方法	优点	缺点
标记数组	O(n) 更优	需要额外数组
排序法	思路直观	O(n log n)

👉 面试/比赛更推荐：标记法

👉 练习排序：可以用这个 👍

5️⃣ 时间复杂度

O(n log n)

---

💻 C++代码（快排实现）

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int a[N], d[N];
int n;

void quick_sort(int l, int r) {
    if (l >= r) return;

    int i = l, j = r;
    int pivot = d[(l + r) >> 1];

    while (i <= j) {
        while (d[i] < pivot) i++;
        while (d[j] > pivot) j--;
        if (i <= j) {
            swap(d[i], d[j]);
            i++, j--;
        }
    }

    if (l < j) quick_sort(l, j);
    if (i < r) quick_sort(i, r);
}

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

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

        if (n == 1) {
            cout << "Jolly\n";
            continue;
        }

        // 计算差值
        for (int i = 1; i < n; i++) {
            d[i - 1] = abs(a[i] - a[i - 1]);
        }

        // 快排
        quick_sort(0, n - 2);

        // 判断
        bool ok = true;
        for (int i = 0; i < n - 1; i++) {
            if (d[i] != i + 1) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "Jolly" : "Not jolly") << '\n';
    }

    return 0;
}

---

⚠️ 易错点

❌ 1. 差值数组长度写错

d 的长度是 n-1，不是 n

❌ 2. 排序区间错误

quick_sort(0, n-1) ❌

✅ 正确：

quick_sort(0, n-2)

❌ 3. 判断条件写错

d[i] == i ❌

✅ 正确：

d[i] == i + 1

🚀 总结（帮你形成套路）

这题两种套路：

✅ 写法1（推荐）

标记数组 → O(n)

✅ 写法2（你现在练的）

排序 → 判断是否为 1~n-1

---

这道题我自己用hashmap写的，可以尝试其他解法 「同一道题的多解法训练体系（标记 / 排序 / 二分 / 双指针）」