题解：洛谷 P1152 欢乐的跳

【题目来源】

洛谷：P1152 欢乐的跳 - 洛谷 (luogu.com.cn)

【题目描述】

一个 \(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。

【输入样例】

4 1 4 2 3

【输出样例】

Jolly

【解题思路】

【算法标签】

《洛谷 P1152 欢乐的跳》 #模拟# #枚举# #排序#

【代码详解】

#include <bits/stdc++.h>
using namespace std;int main()
{int n, a[1005], b[1005] = {0}, mark = 1; // 定义变量：n为序列长度，a存储序列，b用于标记差值是否出现，mark用于判断是否为Jolly序列cin >> n; // 输入序列长度for (int i = 1; i <= n; i++) cin >> a[i]; // 输入序列中的元素// 桶排序实现for (int i = 1; i < n; i++) {int t = abs(a[i] - a[i + 1]); // 计算相邻元素的绝对差值if (t < 1005) b[t] = 1; // 如果差值在合理范围内，标记该差值出现过}// 检查1到n-1的所有差值是否都出现过for (int i = 1; i < n; i++) {if (b[i] == 0) { // 如果某个差值未出现mark = 0; // 标记为不是Jolly序列break; // 提前退出循环}}// 输出结果if (mark) cout << "Jolly"; // 如果所有差值都出现过，输出"Jolly"else cout << "Not jolly"; // 否则输出"Not jolly"return 0; // 程序结束
}

【运行结果】

4 1 4 2 3
Jolly